复杂度¶
时间复杂度¶
算法效率的度量¶
- 事后统计
- 事前分析估算
算法时间取决于算法的控制结构（顺序，循环，分支）和原操作（固有数据类型大的操作）
从算法中选取基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。
时间复杂度：T(n) = O(f(n))
随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同
即算法内的原操作重复执行次数和算法执行时间成正比。
例如：
{++x;} 时间复杂度：O(1)
for(int i = 0; i< n;i++>){++x;} 时间复杂度O(n)
for(int i = 0; i< n;i++>) for(int j = 0; j< n;j++>){++x;}时间复杂度O(n^2)
常见时间复杂度¶
平均时间复杂度¶
所有可能的数据输入集的期望值
最坏时间复杂度¶
最坏情况下的时间复杂度
空间复杂度¶
算法所需空间的度量
空间复杂度：S(n) = O(f(n))