算法複雜-嵌套for循環

for(j=n; j>1; j/=2) 
    ++p; 
for(k=1; k<p; k*=2) 
    ++q;

在第一代碼示例，p可變屬於第一迴路。所以，即使它們沒有嵌套循環，也會第二個返回日誌（n）呢？我的意思是，O（loglog（n））？算法複雜-嵌套for循環

for(i=n; i>0; i--){ 
    for(j=1; j<n; j*=2){ 
    for(k=0; k<j; k++){ 
     //statements-O(1) 
    } 
    } 
}

而且這些中的一個，它們嵌套但ķ變量屬於第二循環。那麼，它應該與第一個類似嗎？類似於O（n^2.log（n））或O（n.log^2（n））？

2017-04-06 Can Dirik

[如何找到時間算法的複雜度（http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm） –

算法：第一個循環取log（n）時間。第二個循環取log（log（n））時間。所以你有log（n）+ log（log（n））。但首先循環更重要。所以它是O（log（n））。算法：首先看看當你只分析兩個外部for循環（表示n log（n））時你有什麼運行時間。但不幸的是，這裏出現了循環內部的三分之一，這使得它更加複雜。

第三個循環計數從0到2^m，其中m = log（n）。所以你必須從0到2^m的總和爲log（n）-1，這是n-1。所以n-1是兩個內部for循環的運行時間。現在，您必須將其乘以外循環的線性運行時間。所以它是（n-1）n是n 2 -n。所以你有三個循環的O（n²）。

2017-04-06 13:05:48 gartenkralle

感謝可能的複製您。現在我明白了第一個問題的返回值和運行時差異。 –

回答