问题
计算该算法的复杂度:
for(i=n; i>1;i=i/2)
for(j=i;j<n;j++){
statement;
}
我之前在这个话题上做了什么:
第一个循环运行 logn 次。第二个循环运行 ni 次, 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).