奇怪嵌套循环的时间复杂度

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

回答