[理工] [資結] heapsort

[doggingg (doggingg)]

Assume an array A contains n integers. The following pseudocode is
used to sort the elements of A by heapsort approach.
The procedures BUILD_HEAP() and HEAPIFY() are used to build and modify
a heap,respectively. Find the time complexity for each statement of
the pseudocode and the total complexity of the algorithm.

Algorithm HEAPSORT(A,n)
        BUILD_HEAP(A,n)
        for i<--n downto 2
        do exchange A[1]<---->A[i]
        HEAPIFY(A,1,i-1)

請問這題該怎麼解，有請神人，謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.116.208.78
→ ybite:（這題需要一些演算法概念，只講結果，原理請有時間再看）
→ ybite:BUILD_HEAP的時間複雜度是O(n)，HEAPIFY的話則是O(lgn)
→ ybite:再加上迴圈是做O(n)次，結果為O(n)+O(n)*O(lgn) = O(nlgn)
→ doggingg:恩，謝謝