如何查找具有內部循環的算法的最壞情況時間複雜度？

int sum = 0; 
for (int i = 1; i < N; i *= 2) 
    for(int j = 0; j < i; j++) 
     sum++;

我將如何找到這個代碼的最壞情況下的時間複雜度？我已經看過很多關於尋找時間複雜性的教程，並且我理解了它們。但是這個與教程中的有些不同。

2017-09-06 TheSaviour

這是不同的，因爲它沒有最壞的情況。 – litelite

真的嗎？爲什麼？ – TheSaviour

你可以製作比其他任何'N'都難的'N'嗎？並非所有的算法都有最壞的情況。 – litelite

讓我們做簡單的數學。每次迭代中i的值爲1,2,4,8... (log N + 1) terms。在每次迭代中，內循環變爲i次。加起來i

T（N）=的值1 + 2 + ... +（日誌N + 1），即術語GP與a = 1和r = 2和n = (log N + 1)

T（N）=α[（ ř^ñ -1）/（R-1）]
= 1 [（2- ^{（logN個+ 1）} - 1）/（2-1）]
= 2N - 1
= O（N ）

所以複雜度在所有情況下都是O（N）。

2017-09-06 18:32:56

您確定序列中的最後一項是logN + 1嗎？假設N = 100。現在我們的價值不能高於N（在這種情況下是100）。所以i的最大值是64.但是如果我們插入100到logN + 1，我們得到3. – TheSaviour

logN + 1是順序的術語，而不是上一項的值。另外，它的日誌到了基地2. –

我明白了。因此，如果內循環代替了'（int j = 0; j TheSaviour

首先考慮一個簡單的情況，當N=2^k+1爲一些整數k。在這種情況下，外循環有k迭代和操作的總體數量是

T(N) = 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 = 2N - 3.

因此，最壞的情況下複雜度至少O(2N - 3) = O(N)。

現在假設2^k + 1 < N <= 2^(k+1)爲一些k。然後

T(N) = 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 < 2N = O(N)

因此T(N) = O(N)。

2017-09-06 18:27:41

回答