題組內容

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

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

詳解 (共 3 筆)

一定會上榜
一定會上榜
詳解 #1727281
2015/12/21
無
HowHow Chen
HowHow Chen
詳解 #1822908
2017/02/02

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

hchungw
hchungw
詳解 #5989921
2023/12/19

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

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

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

空間複雜度：O(k)

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

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