本文介绍了O(N日志log n)的时间复杂度的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

I have a short program here:

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 n)的。为什么会出现这种情况?我得到了整个计划将至少运行n次。但我不知道如何找到loglogN个。内环取决于K * K,所以它显然将是小于n。而且它只是为N日志N,如果它是K / 2各一次。但如何将你找出答案是日志中记录N +

The asymptotic running time of this is O(n log log n). Why is this the case? I get that the entire program will at least run n times. But I'm not sure how to find log log n. The inner loop is depending on k * k, so it's obviously going to be less than n. And it would just be n log n if it was k / 2 each time. But how would you figure out the answer to be log log n?

推荐答案

有关数学证明,内循环可写成:

For mathematical proof, inner loop can be written as:

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)。

and then total time is O(n loglogn).

为什么内环为T(N)= T(开方(N))+1?第一眼看到时,内循环中断,当k> N,意味着在此之前,K是最少的sqrt(N),或在二级之前,它是最多的sqrt(N),因此运行时间为T(开方(N)) + 2&GE; T(N)与GE; T(开方(N))+ 1。

Why inner loop is T(n)=T(sqrt(n)) +1?first see when inner loop breaks, when k>n, means before that k was at least sqrt(n), or in two level before it was at most sqrt(n), so running time will be T(sqrt(n)) + 2 ≥ T(n) ≥ T(sqrt(n)) + 1.

这篇关于O(N日志log n)的时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-23 15:35