如何確定算法的最壞情況複雜度？

我正在爲堆編寫siftup算法，並且我被困在問題的結尾。問題的最後部分說明算法應該具有對數最壞情況時間複雜度，即O(log(n)。我已經在下面寫了算法，其中i是堆中元素的索引，v是堆數組。根的索引是堆中最低的孩子的最低值。我正在考慮的陣列從1轉到步驟n如何確定算法的最壞情況複雜度？

算法

Siftup (v, i) { 
While(v[i] > v[i/2] and i != 0) { 
    Temp = v[i] // Temp is of the same type as v[i] 
    v[i] = v[i/2] 
    v[i/2] = temp 
    i = i/2 
    } 
}

由於處理涉及四個賦值語句在while loop每一個具有恆定的最壞情況下的時間，該算法應具有對數最壞情況時間複雜。任何一個可以顯示一個方法來確定它的O(n)，其中n是堆中元素的數量？

P.S.請讓我知道我的算法中的錯誤。

來源

2013-02-14 Sumit Gera

是的，它看起來像你的算法具有對數複雜性。

我同意你的觀察，即每次迭代似乎具有不變的複雜性。

之後的步驟是找出對於給定的N值將執行多少次迭代。雖然我不打算直接回答這個問題，但這裏的關鍵是i = i/2。這可能更容易反過來看：對於某些給定的N，在它達到N之前，你需要多少次加倍i（從1開始）？更具體地說，N的大小和在至少與N一樣大之前需要加倍i的次數之間的關係是什麼？

來源

2013-02-14 16:00:24

條件'i！= 0'不能達到目的，因爲這是元素值停止篩選的點。 – 2013-02-14 16:02:38

@buzzinga：我不得不考慮一下 - 我認爲它可能有效，但我不確定（當我在C++中編寫了一個heapsort時，我已經欺騙並使用了基於1的索引）。 – 2013-02-14 16:21:28

如何確定算法的最壞情況複雜度？

回答

相關問題