algorithm - 这个小代码片段的大 O 是什么？

Question

for i := 1 to n do
  j := 2;
  while j < i do
    j := j^4;

当涉及到 Big-O 表示法时，我真的很困惑，所以我想知道它是否是 O(n log n)。这是我的直觉，但我无法证明这一点。我知道 while 循环可能比 log n 快，但我不知道快多少!

编辑:插入符号表示指数。

Answer 1

问题是 while 循环针对给定 i 执行的迭代次数.

在每次迭代中 j:= j^4并在开头j := 2 ，所以在 x 之后迭代 j = 2 4^x

j < i相当于x < log_4(log_2(i))

我敢声明，复杂度是 O(n * log_4(log_2(n)))

您可以去掉大 O 表示法中的常数因子。 log_4(x) = log(x) / log(4)和 log(4)是一个常数。同样，您可以更改 log_2(x)至 log(x) .复杂度可以表示为O(n*log(log(n)))