算法分析

算法的时间性能分析

通常有两种衡量算法时间性能的方法

• 事后统计法
• 事前估算法

算法时间分析复杂度

1. 计算算法的频度 $T(n)$

求出算法所有原操作的执行次数。

2. $T(n)用O表示$
   不同的时间复杂度存在以下关系:

$O(1) < O(\log_2n)< O(n) < O(n\log_2n） < O(n^2) < O(2n) < O(n!)$

3. 简化的算法时间复杂度分析
   找出最深的语句分析频度

$T(n) = n^2=O(n^2)$

4. 时间复杂度的求和、求积定理
   为了计算算法的时间复杂度，有以下两个定理。
   求和定理：假设 $T_1(n)$和$T_2(n)$是程序段$P_1$、$P_2$的执行时间，并且$T_1(n)=O(f(n))$，$T_2(n)=O(g(n))$，那么先执行$P_1$，再执行$P_2$的总执行时间$T_1(n)+T_2(n)=O(MAX(f(n),g(n)))$。
   求积定理：假设 $T_1(n)$和$T_2(n)$是程序段$P_1$、$P_2$的执行时间，并且$T_1(n)=O(f(n))$，$T_2(n)=O(g(n))$，那么$T_1(n)\times T_2(n)=O(f(n)\times g(n)$。

算法空间性能分析

算法空间复杂度是对一个算法在运行过程中占用的存储空间大小的量度。只需考虑临时空间，不必考虑形参空间，形参空间会在调用该算法的算法中考虑。一般也作为问题的规模n的函数，以数量级形式给出，记作：

$S(n) = O(g(n))$