问题
计算这个算法的复杂性：
for(i=n; i>1;i=i/2)
for(j=i;j<n;j++){
statement;
}
以前我对此主题做了些什么：
第一个循环运行logn时间.
第二个循环运行n-i次,i从n开始,并在每个外循环迭代中改变为i / 2.所以内循环运行如下：
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)的公式不能应用于它.如何进一步处理此解决方案或错误,那么正确的方法是什么.
注意：如果应用n / 2 *(a l),则得到的复杂度为-n /(2 ^ n)= O(2 ^ n).
解决方法
你在正确的轨道上.正如你所说,内循环将运行日志n次.所以,它运行的总次数是：
(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))
记住,当计算复杂性时,你总是在寻找上限,而不是精确的数字.
