題組內容

四、下列 C 語言函數是氣泡排序演算法 

(三)承(二)，請問計數排序法的時間複雜度和空間複雜度為何？（10 分）

詳解 (共 3 筆)

詳解 提供者：一定會上榜
無
詳解 提供者：HowHow Chen

時間複雜度爲O(N+K)，空間複雜度爲O(N+K)

詳解 提供者：hchungw

計數排序法（Counting Sort）的時間複雜度和空間複雜度如下：

時間複雜度：O(n+k)

  • 其中n是待排序數組的元素數量，k是數據範圍。
  • 對於給定問題中的情況，由於數據範圍k固定為10（數字0到9），時間複雜度可以被視為O(n)。

空間複雜度：O(k)

  • 需要額外的空間來存儲計數數組，其大小與數據範圍k相關。
  • 在這個問題中，由於範圍固定為10，空間複雜度是常數，即O(1)。

因此，計數排序是一種非比較型的排序算法，對於數據範圍不大的情況非常有效。