问题描述
问题
计算此算法的复杂性:
for(i=n; i>1;i=i/2)
for(j=i;j<n;j++){
statement;
}
我之前在这个主题上做了什么:
第一个循环运行登录时间。
第二个循环运行n-i次,i从n开始,并在每个外循环迭代中更改为i / 2。所以内部循环运行如下:
The first loop runs logn times.The second loop runs n-i times with i starting from n and changing to i/2 in each outer loop iteration. So the inner loop runs like this:
n-n 0 times
n - n/2 n/2 times
n - n/4 3n/4 times
n - n/8 7n/8 times
n - n/16 15n/16 times
依此类推
n - 1
次
所以一般术语是 n *((2 ^ n)-1 )/(2 ^ n)
现在这个序列不是算术的,也不是几何的。因此无法在其上应用 n / 2 *(a + l)
的公式。如何进一步处理此解决方案或者如果错误,那么正确的方法是什么。
Now this sequence is not arithmetic nor geometric. So formula of n/2 * (a+l)
cannot be applied on it. How do I further proceed with this solution or if it is wrong, then what is the correct method.
注意:如果 n / 2 *(应用a + l)
,结果复杂度为 -n /(2 ^ n)= O(2 ^ n)。
Note: If n/2*(a+l)
is applied, the resulting complexity is -n/(2^n) = O(2^n).
推荐答案
你走在正确的轨道上。正如您所提到的,内部循环将运行 log n
次。因此,它运行的总次数是:
You are on the right track. As you mentioned, the inner loop would run log n
times. So, the total number of times it runs is:
(n - n/2) + (n - n/4) + ... (log n) times
= n*(log n) - (n/2 + n/4 + n/8 + ... up to 1)
= n*(log n) - n*(1/2 + 1/4 + ...)
<= n*(log n) - n because (1/2 + 1/4 + ...) is 1 even if we take all terms till infinity (G.P)
= n(log n - 1), which is O(n*log(n))
请记住,在计算复杂性时,您总是在寻找上限,而不是确切的数字。
Remember that when calculating complexity, you are always looking for upper bounds, not exact numbers.
这篇关于两个依赖for循环的复杂性,具有log n复杂性的外循环的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!