如何構建堆是O(N)時間復雜度？有人能幫助解釋如何構建堆是O(N)復雜性嗎？將項插入堆是O(log n)，插入重復n/2次(剩余的是葉子，不能違反堆屬性)。因此，這意味著復雜性應該是O(n log n)我想。換句話說，對于我們“堆化”的每一項，到目前為止，對于堆(這是logn級)，它可能必須對每個級別過濾一次。我遺漏了什么？
3 回答
慕沐林林
TA貢獻2016條經驗 獲得超9個贊
A 大分析
build_heapheapifyO(log n)
heapify
2^(h)heapify2^(h ? 1)2^(h ? 2)
O(log n)O(n).
添加回答
舉報
0/150
提交
取消