big-o - 使用伪代码的 O 表示法

Question

for i=1 to n       | n+1
  for j=1 to i^3   | ???
     x=x+1         |

问题：找到语句 x=x+1 执行 n 次的 O 表示法。我对这里的第二个 for 循环感到困惑。我有第一个执行的语句 n+1，但是第一个 for 循环中的 i=1 是否会影响第二个 for 循环语句 i^3？

我对此的回答是 O=n+1。

score 2 · Accepted Answer

如果内部循环中的i^3是 for i Bitwise Xor 3 (11)
O 表示法将是O(n^2)

如果内部循环i^3中的是i 的 3 次方，则
O 表示法将是O(n^4)

在这种情况下，内部 for 循环将运行

(1^3) + (2^3) + (3^3) + ... + (n^3) times
= (n^2 * (n+1)^2) / 4 times
so O(n^4)

score 1 · Accepted Answer

for i=1 to n

显然有n迭代。在第二行：

for j=1 to i^3

每次迭代运行i^3次数。由于在每次迭代中i增加 1，从 1 开始直到n，算法的运行时间可以表示为所有内循环迭代的总和：

Sum_i=1_i=n(i^3)

总和等于：

(n^2 * (n + 1)^2) / 4

所以你有了：

O((n^2 * (n + 1)^2) / 4)

当尽可能简化上述内容时（请记住，非零常数的乘法或除法，或与常数的加法在大哦符号中将被忽略）我们得到答案：

O(n^4)

2 回答 2