algorithm - 计算大 O 符号

Question

我目前有以下伪代码，我想弄清楚为什么问题的答案是 O(n)。

sum = 0;
for (i = 0; i < n; i++) do
    for (j = n/3;j < 2*n; j+= n/3) do
        sum++;

我认为答案是 O(n^2)，因为第一个 for 循环会运行 'n' 次，而第二个 for 循环有 += n/3，给它另一个(n 除以某次)，这只会简化为 O(n^2)。有人可以解释为什么它是 O(n) 吗？

Answer 1

这是因为第二个循环以恒定的操作量运行(不依赖于n)。从 n/3 到 2n 有一个步骤 n/3 类似于从 1/3 到 2，步长 1/3。

对于合理的 n(不是 0)，这将运行 5-6 次(这个数字并不重要，取决于你如何计算 /)