如何分析這段代碼的複雜性？

我正在從代碼解決problem。根據editorial，以下代碼的複雜度應該是O（n）。如何分析這段代碼的複雜性？

for(int i = n - 1; i >= 0; --i) { 
    r[i] = i + 1; 
    while (r[i] < n && height[i] > height[r[i]]) 
     r[i] = r[r[i]]; 
    if (r[i] < n && height[i] == height[r[i]]) 
     r[i] = r[r[i]]; 
}

這裏，height[i]是i個山的高度和r[i]是第一右山比height[i]更高的位置，並且是height[0]高度陣列的其它值中的最大的總。

我的問題是，我們如何保證代碼的複雜性是O（n），雖然內部while循環的存在？

在inner while循環中，代碼更新r[i]值，直到height[i]>height[r[i]]。並且更新的數量取決於高度數組。例如，按非遞減順序排列的高度數組的更新次數將與按非遞增順序排列的高度數組的排列次數不同。（在這兩種情況下，我們將排列除height[0]之外的數組，因爲height[0]在此問題中應始終爲最大值）。

是否有任何方法來分析這樣的輸入數據變化的算法？攤銷分析將是答案之一？

PS。我想更多地闡明我的問題，我們要在循環中設置數組r []。那這個呢？如果數組height = {5,4,1,2,3}和i=1，（r[2]=3,r[3]=4，因爲2是第一個大於1的值，而3是第一個大於2的值），我們將4與1進行比較，並且因爲4> 1，我們繼續試圖比較4和2（= height[r[2]]），4與3（= height[r[3]]）。在這種情況下，我們必須比較4次來設置r [1]。比較次數與height = {5,1,2,3,4}不同。我們仍然可以保證代碼的複雜性是O（n）嗎？如果我錯過了什麼，請讓我知道。謝謝。

來源

2013-05-29 MS.Kim

我用簡單的例子試過了上面提到的算法，但似乎沒有改變，我錯過了什麼嗎？

例子：

n = 5 
height = { 2, 4, 6, 8, 10 } 
r = { 1, 2, 3, 4, 5 } 

---- i:4 ---- 

r[4] < 5 ? 

---- i:3 ---- 

8 > 10 ? 
8 = 10 ? 

---- i:2 ---- 

6 > 8 ? 
6 = 8 ? 

---- i:1 ---- 

4 > 6 ? 
4 = 6 ? 

---- i:0 ---- 

2 > 4 ? 
2 = 4 ? 

------------- 

height = { 2, 4, 6, 8, 10 } 
r = { 1, 2, 3, 4, 5 }

來源

2013-05-29 08:59:09

你的算法中（我不知道是否會解決你的問題）實際上是O（n），即使有一個內部循環，但在大多數的情況下，由於給定條件，內部循環將不會執行。所以在最壞的情況下，它會像2n那樣運行，即O（n）。

你可以用這樣的方法，其中將返回的時間數它的內部循環被執行檢驗這一假設：平均情況

int arr[] = {1, 2, 3, 4, 5}; 
    do { 
     int count = yourMethod(arr, 5); 
    }while(next_permutation(arr, arr+5));

有了這個，你就可以檢查最壞的情況下，等。

來源

2013-05-29 11:41:27 sowrov

如何分析這段代碼的複雜性？

回答

相關問題