怎么求算法的时间复杂性的上界和下界？

Question

怎么求算法的时间复杂性的上界和下界？
如题
估算下列程序段所代表的算法的时间复杂性的上界和下界：
（1）for(i=1;i<=n;i++){x=x+y;y=x+y;}
(2) while(n>1){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)