雙循環的複雜性

我想弄清楚使用大O表示法for循環的複雜性。我之前在其他課上做過這個，但是這個比其他課更加嚴格，因爲它是基於實際的算法。代碼如下：雙循環的複雜性

for(cnt = 0, i=1; i<=n; i++) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     cnt++; 
    } 
}

和

for(cnt = 0, i=1; i<=n; i*=2) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     cnt++; 
    } 
}

我已經到達第一環是O（n）的複雜性，因爲它會通過列表n次。至於第二圈，我有點失落。我相信對於每個被測試的n，它都會經歷循環。我（錯誤地）認爲這意味着每次評估時循環都是O（n * i）。在我的假設中有什麼是我錯過的。我知道cnt ++是恆定的時間。

謝謝你在分析中的幫助。每個循環都在自己的空間中，它們不在一起。

來源

2012-09-11 Michael Guantonio

第一個樣本不在O（n）中，您是否嘗試在循環後使用不同的n值打印cnt？ – Kwariz

@Kwariz我道歉。我的意思是第一個例子中第一個最外層的循環是O（n）。在第一個例子中，不是整個double for循環的集合。 –

第一個示例的外部循環執行n次。對於外部循環的每次迭代，內部循環執行的次數爲i，所以整體複雜度可以計算如下：第一次迭代一次加二次第二次迭代加三次第三次迭代等等，加上n第n次迭代。

1+2+3+4+5+...+n = (n*(n-1))/2 --> O(n^2)

第二個例子是棘手：因爲每次迭代i雙打中，外環僅執行Log2(n)倍。假設n是2功率，總的內部循環是

1+2+4+8+16+...+n

是2^Log2(n)-1 = n-1爲複雜O(n)。

對於n S中的不二的冪迭代的確切數目爲(2^(Log2(n)+1))-1，這仍然是O(n)：

1  -> 1 
2..3 -> 3 
4..7 -> 7 
8..15 -> 15 
16..31 -> 31 
32..63 -> 63

等。

來源

2012-09-11 18:39:18 dasblinkenlight

儘管如何將第二個示例中的兩個循環組合起來？它是一個增加的複雜性，因此它總體上是O（n），還是一起乘以給出O（n log n）還是其他的東西？ –

@JBKing計算第二對循環的big-O會更容易，因爲在這種情況下，我們可以使用[衆所周知的幾何級數前N個元素的總和]（http ：//en.wikipedia.org/wiki/Geometric_progression），它是'a *（1-r ^（N + 1））/（1-r）'。在我們的例子中，'a = 1'和'r = 2'，所以結果是'（1-2 ^（n + 1））/（1-2）'或者'2 ^（n + 1） 1'。 – dasblinkenlight

但願這不是功課，但我不知道你至少做此嘗試，所以這是我拿到這個：

cnt遞增N *（N + 1）/ 2次，這使兩個循環的整個集合爲O（n^2）。第二個循環平均爲O（n/2），即O（n）。

來源

2012-09-11 18:37:31

對於第二個樣本，增量不是+2，但是我增加了一倍...這種味道不應該像日誌一樣複雜嗎？ – Kwariz

第一個例子是O（N^2），並且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?將是答案的問題，其中關鍵是要注意內循環的循環數取決於n。

第二個例子是有可能爲O（n log n）的自外部循環遞增在不同的規模比線性的。查看二分查找對數複雜情況的例子。在第二個例子中，外部循環是O（log n），內部循環是O（n），它們相結合產生O（n log n）複雜度。

來源

2012-09-11 18:40:12

第二個循環是'O（n）'，因爲內循環上升到'i'，而不是'n'，並且'i'通過'2'的冪直到'Log2（n）'。 – dasblinkenlight

雙循環的複雜性

回答

相關問題