具有嵌套while循环的算法的时间复杂度计算

Question

我正在尝试计算以下程序的时间复杂度。到目前为止，我的计算得出最坏情况的时间复杂度为 O(n^3)。

for i in range(1, n):
  j = 1
  while j < i*i:
    j += 1

我的方法涉及创建一个表并计算每个循环的“运行”次数。

因此，对于任意 N，外循环将循环 (N-1) 次，内循环将总共循环 ((N-1)/2)*(0+(N-1) )^2 - 1)，这里我用的是等差级数求和公式。将它们相加得到 O(n^3) 复杂度。

我想我想问的是算法是否有可能只需要两个循环就具有 O(n^3) 复杂度。我认为理论上应该是可能的，时间复杂度只是算法的运行时间与输入大小成正比的估计，但是，我还没有看到这样的算法，其中两个循环会产生这样的答案。

Answer 1

O(n3) 是正确的。

复杂性与嵌套循环的数量没有直接关系，即使这通常是一个很好的指标;-)。

例如

for i in range(1, n*n*n*n*n*n):
  a++;

有 O(n⁶)，只有 1 个循环。