有關堆疊排序法(heap sort)的敘述,何者錯誤?

老師出的另外一題不會的

攸關我期末會不會過~

拜託厲害的大家

幫我一下吧

要寫出選項錯或對的原因喔~拜託拜託~

以下有關堆疊排序法(heap sort)的敘述,何者錯誤?

(A)其最差情況(worst case)的時間複雜度(time complexity)為O(nlogn)

(B)其平均情況(average case)的時間複雜度(time complexity)為O(nlogn)

(C)其最佳情況(best case)的時間複雜度(time complexity)為O(l)

(D)除資料本身外,其所需額外空間的空間複雜度(space complexity)為O(l)

1 Answer

Rating
  • 1 decade ago
    Favorite Answer

    Heap Sort 最差 平均最佳 時間複雜度都是O(N log N)

    所以錯的是C

    2006-06-21 23:37:57 補充:

    Name............Average.Case....Best.Case.......Worst.CaseBubble.Sort.....O(N2)...........O(N2)...........O(N2)Insertion.Sort..O(N2)...........O(N)............O(N2)Shell.Sort......O(N1.5).........O(N)............O(N1.5)Selection.Sort..O(N2)...........O(N2)...........O(N2)

    2006-06-21 23:38:17 補充:

    Merge.Sort......O(N.log.N)......O(N.log.N)......O(N.log.N)Quick.Sort......O(N.log.N)......O(N.log.N)......O(N2)Radix.Sort......O(N)............O(N)............O(N)Heap.Sort.......O(N.log.N)......O(N.log.N)......O(N.log.N)

Still have questions? Get your answers by asking now.