一个语句的频度是指该语句在算法中被重复执行的次数。
算法中所有语句的频度之和记为T(n)，它是该算法问题规模 的函数
时间复杂度主要分析 T(n)的数量级
算法中基本运算 (最深层循环内的语句)的频度与 T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此，算法的时间复杂度记为
T(n)= O(f(n)))
算法的时间复杂度不仅依赖于问题的规模 n，也取决于待输入数据的性质(如输入数据元素的初始状态)。
最坏时间复杂度是指在最坏情况下，算法的时间复杂度。
平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
最好时间复杂度是指在最好情况下，算法的时间复杂度。
一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。
常见的渐近时间复杂度为
O(1)< O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³)< O(2ⁿ) < O(n!) < O(nⁿ)
一些算法的时间复杂度
void fun(int n)int i = 1while(i<=n)i = i*2
O(log₂n)
x=2;
while(x<n/2)x=2*x;
O(log₂n)
求整数 n(n20)的阶乘的算法如下
int fact(int n){if(n<=l) return 1;return n*fact(n-1);
}
O(n)
count=0;
for(k=1;k<=n;k*=2)for(j=l;j<=n;j++)count++;
嵌套循环，内层和外层的循环，如果遍历不同，则各自独立互不相关，得到内外层的时机复杂度后再相乘
O(nlog₂n)
int func(int n){int i=0，sum=0;while(sum<n) sum += ++i;return i;
}
求和算法的时间复杂度 O(n½)
void fun(int n){int i=0;while(i*i*i<=n)i++;
}
O(n开三次方)
归纳总结
此类问题有两种形式：
1.循环主体中的变量参与循环条件的判断
此类题应该找出主体语句中与 T(n)成正比的循环变量，将之代入条件中进行计算。例如:
int i=1;
while(i<=n)i=i*2;
i乘以2的次数正是主体语句的执行次数，因此有 2的t次方 ≦n，取对数后得t ≦ log₂n，则T(n)= 0( log₂n)。
2.循环主体中的变量与循环条件无关此类题
可采用数学归纳法或直接累计循环次数。多层循环时从内到外分析，忽略单步语句、条件判断语句，只关注主体语句的执行次数。
此类问题又可分为递归程序和非递归程序:
递归程序一般使用公式进行递推。例如习题 5 的时间复杂度分析如下:
T(n)=1+T(n -1)=1+1+ T(n -2)=··=n-1+ T(1)
即 T(n)= O(n)。
非递归程序比较简单，可以直接累计次数，
