問題詳情

48. 假設要排序 n 個數字，且每個數字的範圍介於 1 到 n 之間，請問下列何者敘述不正確？
(A)使用 Heap Sort 可在 O(n log n) 的時間複雜度完成
(B)使用 Radix Sort 可在 O(n) 的時間複雜度完成
(C)使用 Merge Sort 最壞的情況下需要 O(n log n) 的時間複雜度，但根據輸入的不同，有可能在某些情況下達到更快的時間複雜度
(D)使用 Quick Sort 在最壞的情況下會需要 Θ (n^2) 的時間複雜度

參考答案

答案：C
難度：困難0.352941
統計：A(9),B(14),C(24),D(9),E(0)

用户評論

【澐】評論

演算法時間複雜度空間複雜度穩定性類型BestWorstAvg選擇排序法(Selection Sort)Ο(n2)Ο(n2)Ο(n2)Ο(1)不穩定選擇插入排序法(Insertion Sort)Ο(n)Ο(n2)Ο(n2)Ο(1)穩定插入氣泡排序法(Bubble Sort)Ο(n)Ο(n2)Ο(n2)Ο(1)穩定交換謝爾排序法(Shell Sort)Ο(n)Ο(n2)~ Ο(n1.5)Ο(n5/4)Ο(n) + Ο(1)不穩定插入搖晃排序法(Shaker Sort)Ο(n)Ο(n2)Ο(n2)Ο(1)穩定交換快速排序法(Quick Sort)Ο(n log n)Ο(n2)Ο(n log n)Ο(log n)~Ο(n)不穩定交換合併排序法(Merge Sort)Ο(n log n)Ο(n log n)Ο(n log n)Ο(n)穩定合併堆積排序法(Heap Sort)Ο(n log n)Ο(n log n)Ο(n log n)Ο(n) + Ο(1)不穩定選擇基數排序(Radix Sort)Ο(d×(n+r))Ο(d...