循環的時間複雜度乘以兩或三的值

Question

我在SO問題中找到了下面的for循環。

我發現時間複雜度是O(n log n)。

如果我們將k *= 2更改爲k *= 3，我將如何找到時間複雜度？

// 'int n' is defined somewhere 
int var = 0; 
for (int k = 1; k <= n; k *= 2) 
    for (int j = 1; j <= n; j++) 
     var++; 

Answer 1

時間複雜度仍然是O(n log n)。

對於k *= 2，所述log將基座2

對於k *= 3，所述log將基座3

但是變化的log基座僅影響由一個常數因子的結果（這可以來源於logba = logca/logcb，對於任何基數爲c），這在大O符號中被忽略，因此它們具有相同的時間複雜度。

---

我們從哪裏得到log2n？

嗯，k值是這樣的：

1, 2, 4, 8, 16, ..., 2m for some m, where 2m <= n < 2m+1 
= 20 + 21 + 22 + ... + 2m 

當然這裏面有只m+1（0到m）上述條款，因此該循環運行m+1倍。現在

，如果我們可以用一些基本的對數，以獲得m在n方面：

2m = c.n for some constant c, where 1 <= c < 2 
log22m = log2(c.n) 
m log22 = log2(c.n) 
m.1 = log2c + log2n 
m = O(log2c + log2n) 
    = O(log2n)    // constant terms can be ignored 

我們也可以僅僅通過更換3遵循2完全相同的方法和上面的k *= 3。

Answer 2

答案是N×登錄 N.

想知道爲什麼，你需要弄清楚爲什麼的答案，原來的問題是N×登錄 N.多少次（姑且稱之爲它k）它會執行？它將根據需要執行多次，以自行乘以2，以便結果超過N。換言之，2 ^ķ> N.現在應用對數表達式（對數的定義，可以發現here）的兩側看到k>登錄 N.

的，我們使用的理由作爲對數的基礎的2是指數在左邊的基數是2。很容易看出，如果exponen的基數是3，則應用日誌可以爲您解決的問題提供答案。

Answer 3

可以進行正式的和有條不紊適馬符號：

檢查此document的最後一張幻燈片。