我目前有以下伪代码，我想弄清楚为什么问题的答案是 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) 吗？
最佳答案
这是因为第二个循环以恒定的操作量运行(不依赖于n)。从 n/3 到 2n 有一个步骤 n/3 类似于从 1/3 到 2，步长 1/3。
对于合理的 n(不是 0)，这将运行 5-6 次(这个数字并不重要，取决于你如何计算 /)
关于algorithm - 计算大 O 符号，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34113015/