这个小代码片段的大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 = 24^x

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

我冒险发表声明,复杂性是 O(n * log_4(log_2(n)))

你可以摆脱Big O符号中的常数因素.log_4(x) = log(x) / log(4)并且log(4)是一个常数.同样你可以log_2(x)改为log(x).复杂性可以表示为O(n*log(log(n)))