我在这里有一个简短的程序：
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次。但是我不确定如何找到日志log n。内部循环取决于k * k，因此显然要小于n。如果每次是k / 2，那将只是n log n。但是您如何确定答案是log log n？
为了进行数学证明，内循环可以写为：
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）之前，或者在k等于最大sqrt（n）之前处于两个级别，因此运行时间为T（sqrt（n））。 + 2≥T（n）≥T（sqrt（n））+ 1。
