二、算法的渐进分析

以算法的时间代价为例，算法的渐进分析就是估计当求解问题的规模 n 逐步增大时，时间开销 T(n) 的增长趋势。为简化时间和空间复杂性的度量，可以只关注于复杂性的量级，而忽略量级的系数。而从数量级大小来考虑，当 n 增大到一定值以后，T(n) 计算公式中影响最大的就是 n 的幂次最高的项，其他的常数项和低幂次项都是可以忽略的。
    渐进分析的结果是得到一个大 O 渐进表达式， 简写为

    其中，T(n) 是算法运行所消耗的时间或存储空间的总量，O 是数学分析常用的符号“大O”，f(n) 是自变量为 n 的某个具体的函数表达式，n 反映求解问题的规模。也即，如果存在正的常数 c 和 ，当问题的规模后，某算法的时间（空间）代价，则说该算法的时间（空间）代价为。

    根据大 O 表示法的定义，有下列常用的计算规则：
    （1）       加法规则 设有两个程序段S₁ 和S₂，其时间代价分别为和，将两个程序段连接在一起得到（S₁ ：S₂），则总的时间代价为
    （2）       乘法规则  假设有 和，如果一个程序的时间代价为，但其时间单位并不是最基本的，而是以某个子程序的执行代价为单位时间（）来考虑的，那么这个程序的实际时间代价为