一个算法的时间复杂度（嵌套循环）

Question

我正在尝试计算这个伪代码所代表的算法的时间复杂度：

sum = 0;
for (i = 1; i <= n; i++)
    for (j = 1; j <= n / 6; j++)
        sum = sum + 1;

我知道第一行会运行n次，但我不确定第二行。

- Aede

---

时间复杂度 = 总和 ? :) (n*n/6) - Danny_ds

那不就是O(n^2)吗？看起来太简单了。 - Aede

是的 @Aede，你有没有检查答案，它们解释了这个问题。 :) - gsamaras

没问题，谢谢。 - Aede

哦，好的，我的错，忘记了！顺便问一下，这是个好问题，所以我会点赞，因为这是你第一次提问，请确保下次在 Stack Exchange 的适当站点发布适当的问题。 :) - gsamaras

Answer 1

使用Σ符号，我们可以得出您的算法的渐近界限如下：

- dfrib

Answer 2

这里有一个简单的双重循环：

for i=1;i<=n;i++
   for j=1; j<=n/6; j++

如果你计算循环体将被执行的次数（即这行代码 sum = sum + 1; 将被执行的次数），你会发现它是:

n*n/6 = n²/6

以大O符号表示，它是：

O(n²)

因为我们不关心常数项，因为随着 n 的增长，常数项是否存在都没有（大）区别！

---

只有当你完全意识到我所说的，你才能深入探究这个好问题：Big O, how do you calculate/approximate it?

---

但请注意，这样的问题更适合于理论计算机科学，而不是SO。

- gsamaras

Answer 3

你需要进行n*n/6次操作，因此时间复杂度为O(n^2/6) = O(n^2)。

- Gabriel Ilharco

---

更准确地说，n * (n / 6) 次操作：复杂度相同，但结果不同。 - chqrlie