以下代码的渐近复杂度是多少

Question

我对下面代码的复杂度有些疑惑外层循环将执行 O(N) 次我怀疑内部循环是要执行 O(1) 还是 O(n)

for (int i=0; i<n; i++)
for (int j=i; j< i; j+=i) 
{ 
print(“*”);
}
}

Answer 1

内部是O(i)，每次递增，所以全局复杂度为：内循环执行次数：1+2+3+...+n，即：

因此 O(n^2)

Answer 2

因为 j 在内部循环中被初始化为 i，所以该循环永远不会执行，因为条件要求 j 小于 i。因此，复杂度为 O(n)：所有这一切只是在外循环中递增 i 并在外循环体的每次迭代期间验证 i 不小于 i.

Answer 3

正如有人指出的那样，代码内部循环将执行 0 次，所以我假设你的意思是：

for (int i=0; i<n; i++)
{
  for (int j=0; j<n; j+=i) 
  { 
    print(“*”);
  }
}

那么，在后续的外循环执行中，内循环的执行次数为N, N/2, N/3, N/4, ...。所以总时间将为 N + N/2 + N/3 + ... = N * (1 + 1/2 + 1/3 + ...)。现在，我们可以看到 (1 + 1/2 + 1/3 + 1/4 + ...) <= (1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + ...)。对于每个额外的 1/2，第二个表达式需要两倍的项（例如，您需要两倍于 1/4 的 1/8 来生成 1/2），因此它将是 O(logN)。所以总的复杂度是 O(N*logN).

以下代码的渐近复杂度是多少

What is the asymtotic complexity of the following code

complexity-theory