嵌套循环的大O时间复杂性

Question

以下代码的时间复杂度是多少？

int i = 0;
while(i*i <=N) {
  for(int j = 0; j <=N; j++) {
    for(int k = 0; k <=N; k++, i++) {
      //O(1) operation
    }
  }
i++;
}

在嵌套循环中，如果外循环1需要O（1）时间，内循环2需要O（logn）时间，内循环3需要O（n）。那么总的tc是O（1）O（logn）O（n）=O（nlogn）。这是真的吗？

请解释一下。

Answer 1

嵌套循环的大O时间复杂性

操作“//O（1）操作”被执行（n1）^2次。以及循环本身进行计算的次数（例如，执行测试j

所以时间复杂度是O（N^2）。

您可以通过以下方式扩展您的程序来测试：

int i=0;
int count=0;
while(i*i <= N)
{
    for(int j=0; j<=N; j++)
    {
        for(int k=0; k<=N; k++, i++)
        {
            count++;
        }
    }
    i++;
    printf("i after the while() loop: %d\n",i);
}
printf("Number of steps: %d\n",count);

使用不同的N值测试程序，可以看到：

• i是（n1）^21在while（）循环的第一次通过之后。这意味着条件i*i

时间复杂性

此类问题通常在CS Stack Exchange网站上提出，而不是在StackOverflow上。

StackOverflow仅适用于有关编写计算机程序的问题。

（请注意，StackOverflow是StackExchange网络的一部分，您可以使用您的用户帐户使用所有StackExchange网站。）

Answer 2

tl； dr：这段代码在O（n^2）中运行。

详细答案：
外环：而（i*i

因为i在最内部循环的每一次迭代中都会自我增加，这意味着当你重新评估其中的条件时，i的值将是N*N。这意味着，外部循环总是只重复一次。

现在，一旦你忽略它，很容易看到剩余代码的时间复杂度是O（N^2），因为它基本上可以重写为：

int i = 0;
if (i * i <= N) {  // Since the while loop does not repeat more than once
  for(int j = 0; j <=N; j++) {
    for(int k = 0; k <=N; k++, i++) {
      //O(1) operation
    }
  }
  i++;
}

注意：这个答案假设变量没有溢出，特别是i没有溢出