O(n log log n)时间复杂度

Question

我这里有一个简短的程序:

Given any n:
i = 0;
while (i < n) {
   k = 2;
   while (k < n) {
        sum += a[j] * b[k]
        k = k * k;
   }
   i++;
}

这个的渐近运行时间是O(n log log n).为什么会这样？我知道整个程序至少会运行n次.但我不知道如何找到日志日志n.内循环取决于k*k,所以它显然小于n.如果每次都是k/2那么它就是n log n.但是你怎么能找到答案是log log n？

Answer 1

对于数学证明,内循环可以写成:

T(n) = T(sqrt(n)) + 1

w.l.o.g assume 2 ^ 2 ^ (t-1)<= n <= 2 ^ (2 ^ t)=>
we know  2^2^t = 2^2^(t-1) * 2^2^(t-1)
T(2^2^t) = T(2^2^(t-1)) + 1=T(2^2^(t-2)) + 2 =....= T(2^2^0) + t =>
T(2^2^(t-1)) <= T(n) <= T(2^2^t) = T(2^2^0) + log log 2^2^t = O(1) + loglogn

==> O(1) + (loglogn) - 1 <= T(n) <= O(1) + loglog(n) => T(n) = Teta(loglogn).

然后总时间为O(n loglogn).

为什么内环是T(n)= T(sqrt(n))+1？ 首先看内部循环中断时,当k> n时,表示k之前至少为sqrt(n),或者在最多为sqrt(n)之前的两个级别,因此运行时间将为T(sqrt(n)) +2≥T(n)≥T(sqrt(n))+ 1.