怎么求算法的时间复杂性的上界和下界?如题估算下列程序段所代表的算法的时间复杂性的上界和下界：（1）for(i=1;i1){if(n%2)n=n-1;elsen=n/2;

Question

怎么求算法的时间复杂性的上界和下界?
如题
估算下列程序段所代表的算法的时间复杂性的上界和下界：
（1）for(i=1;i1){if(n%2) n=n-1;else n=n/2;

Answer 1

简单一点,忽略诸如程序在循环变量上的开销,只考虑循环体
复杂度是通过数运算次数直接数出来的,要知道循环多少次,以及每次循环的工作量
(1)循环n次,每次两步加法两步赋值,简单一点讲就是每次循环工作量都是常数,所以复杂度就是Θ(n)（既是上界也是下界）
对于(2)而言,n=n-1下降比较慢,n=n/2下降比较快,同样每次循环的工作量都是常数,只要看循环次数,所以从前者去统计上界,从后者统计下界
最少的情况来自n=2^k的形式,要循环k步,复杂度下界是Ω(log n)
循环次数比较多的情况是反复出现n=n-1运算的情况,但注意一旦执行该运算之后n一定变成偶数,所以最坏情况是n=n-1和n=n/2交替出现,此时循环次数不超过2log_2 n,复杂度上界是O(log n)
合并起来总体的复杂度还是Θ(n)