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

Question

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

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

我知道第一行运行

n次

但我不确定第二行。

Answer 1

你进行了 n*n/6 次操作，因此，时间复杂度是 O(n^2/6) = O(n^2).

Answer 2

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

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

因此，如果您计算循环体将被执行多少次（即这行代码 sum = sum + 1; 将被执行多少次），您将看到：

n*n/6 = n²/6

用 big-O 表示法表示是：

O(n²)

因为我们并不真正关心常数项，因为随着 n 的增长，常数项存在与否都没有（大）差异！

何时且仅当你完全明白我在说什么，你可以更深入地回答这个好问题：Big O, how do you calculate/approximate it?

但是，请注意，此类问题更适合 Theoretical Computer Science，而不是 SO。

Answer 3

使用 Sigma 符号，我们可以找到算法的渐近边界如下：

Time Complexity of an Algorithm (Nested Loops)