奇怪嵌套循環的時間複雜度

for(i=1;i<n*n;i++) 
    for(k=1,l=1;l<n;k=k+2,l=l+k) 
     foo;

我該如何估計這樣的構造的時間複雜度？在這個循環奇怪嵌套循環的時間複雜度

2011-12-30 mrjames

尋找由循環：

外環是從1到n的平方，因此O(n^2)
內環是從1到n但步驟是1,4，9，16 .. 。而不是1，2，3，4 ...，因此O(sqrt(n))

嵌套循環繁殖的複雜性，所以我們去O(sqrt(n)*n^2)或O(n^2.5)

2011-12-30 03:02:06 ridecar2

雖然l爲而不是在內部循環中以恆定速率遞增 - 我認爲它更像內部循環的O（sqrt（n））。 – 2011-12-30 03:03:26

公平點，現在編輯答案。 – ridecar2 2011-12-30 03:07:09

一般ridecar2是正確的，但要小心，因爲有時候你可以得到一個詭計問題，例如您的數據的大小是N * N陣列，這意味着陣列的迭代是O（n）不是O（N^2）儘管它看起來像：

for(int i=0; i<n; i++) 
for(int j=0; j<n; j++) 
    doStuff();

2011-12-30 03:10:37 Mr1159pm

我會把整個事情都寫成'O（n^2）'，我會說得對嗎？ – ridecar2 2011-12-30 03:12:09

你指的是我的還是他的？我的例子絕對是O（n），但在他的情況下，n不一定是數據的大小，所以我建議小心。 – Mr1159pm 2011-12-30 03:16:57

你的，因爲它是一個循環，在另一個循環內執行n次，執行n次，產生'O（n^2）' – ridecar2 2011-12-30 03:20:17

你的算法可以被簡化如下所示：

for (i = 1; i < n * n; i ++) 
    for (l = 1 ; l * l < n ; l = l ++) 
     foo;

因此，可使用Sigma公司符號正式推斷的生長複雜的確切順序，如以下表示它：

enter image description here

2014-03-30 15:44:38

回答