嵌套循環的大O，有不同的迭代？

我在計算迭代依賴於外部循環的兩組代碼示例的Big O運行時遇到了一些麻煩。我對Big O運行時間有了基本的瞭解，並且我可以計算出更簡單的代碼示例的運行時間。我不太確定某些線路是如何影響運行時間的。嵌套循環的大O，有不同的迭代？

我會考慮這第一個O（n^2）。但是，我不確定。

for(i = 1; i < n; i++){ 
for(j = 1000/i; j > 0; j--){ <--Not sure if this is still O(n) 
    arr[j]++; /* THIS LINE */ 
} 
}

我對這個有點失落。 O（n^3）可能是O（n^2）？

for(i = 0; i < n; i++){ 
for(j = i; j < n; j++){ 
    while(j<n){ 
     arr[i] += arr[j]; /* THIS LINE */ 
     j++; 
    } 
} 
}

我發現這個職位和我申請這第一個代碼示例，但我仍然不能確定第二。 What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?

來源

2017-07-26 below_avg_st

對於第二個循環（看起來你仍然需要一個答案），你有一些令人誤解的代碼，在那裏你有3個嵌套循環，所以乍一看，它是有意義的運行時是O（n^3）。

但是，這是不正確的。這是因爲最內層的while循環會修改j，這與for循環修改的變量相同。這段代碼實際上相當於該位的代碼如下：

for(i = 0; i < n; i++){ 
    for(j = i; j < n; j++){ 
    arr[i] += arr[j]; /* THIS LINE */ 
    j++; 
    } 
}

這是因爲在裏面while循環運行，增加Ĵ直到Ĵ== n，那麼它打破了。此時，inner for循環將再次遞增j並將其與n進行比較，在那裏它會找到j> = n並退出。您應該已經熟悉這個案例，並將其識別爲O（n^2）。

只需要注意，代碼的第二位並不安全（技術上），因爲當while循環結束運行後，如果您增加一個額外時間，j可能會溢出。這會導致for循環永遠運行。但是，這隻會在n = int_max（）時發生。

來源

2017-07-26 01:50:52 UnknowableIneffable

關於第一個。這是不是O(n^2) !!!爲了簡化和可讀性起見，讓我們把它改寫在僞碼的形式：現在

for i in [1, 2, ... n]:        # outer loop 
    for j in [1, 2, ... 1000/i]:      # inner loop 
     do domething with time complexity O(1).  # constant-time operation

，恆定時操作的內側環路（其依賴於外環的參數i）內的數目可以是表現爲：

現在，我們可以計算出恆定時操作的總體數量：

這裏，N(n)是諧波數（見wikipedia），並有一個非常有趣的，這些數字財產：

哪裏C是Euler–Mascheroni constant。因此，所述第一算法的複雜度是：

關於第二個。看起來好像代碼中包含錯誤，或者它是一個技巧性測試問題。該代碼解析爲

for (i = 1; i < n; i++) 
    for(j = i; j < n; j++){ 
     arr[j]++; 
     j++; 
    }

內環採用

操作，因此我們可以計算出總的複雜性：因爲它可以解決

來源

2017-07-26 02:18:50 FalconUA

這應該是公認的答案OP對問題1的錯誤回答。 – meowgoesthedog

@meowgoesthedog同意 – UnknowableIneffable

嵌套循環的大O，有不同的迭代？

回答

相關問題