1.4 算法分析

1.4.1 科学方法

• 细致地观察真实世界的特点，通常还要有精确的测量
• 根据观察结果提出假设模型
• 根据模型预测未来的事件
• 继续观察并核实预测的准确性
• 如此反复直到确认预测与观察一致

科学方法中必须遵守的，设计的实验可重复性，可证伪性

1.4.2 观察

运行时间的测量

首先需要对程序的运行时间进行测量

/* 计时器 */
class MyTimer{
    private:
    clock_t st;

    public:
    MyTimer();
    void StartTimer();
    double StopWatch();
    ~MyTimer();
};

1.4.3 数学模型

一个程序的运行总时间主要和两点有关：

• 执行每条的耗时
• 执行每条语句的频率

前者取决于计算机、编译器和操作系统，后者取决于程序本身和输入。

近似

用最高次项来对算法时间进行估计，当样本足够大时，高次项对于时间的影响最大

近似运行时间

对增长数量级的估算

算法的分析

成本模型

我们使用术语命题来表示在某个成本模型下算法的数学性质。在全书中我们都会使用某个确定的成本模型研究所讨论的算法。我们希望通过明确成本模型使给定实现所需的运行时间的增长数量级和它背后的算法的成本的增大数量级相同（换句话，成本模型应该和内循环中的操作相关）

总结

对于大多数程序，得到其运行时间的数学模型所需的步骤如下：

• 确定输入模型，定义问题的规模；
• 识别内循环；
• 更具内循环中的操作确定成本模型;
• 对于给定的输入，判断这些操作的执行频率

1.4.4 增长数量级的分类

• 常数级别 $1$
• 对数级别 $\log N$
• 线性级别 $N$
• 线性对数级别 $N\log N$
• 平方级别 $N^2$
• 立方级别 $N^3$
• 指数级别 $2^N$

1.4.5 设计更快的算法

1.4.6 倍率实验

1.4.7 注意实现

1. 大常数

2. 非决定性的内循环

3. 指令时间

4. 系统因素

5. 不分伯仲

6. 对输入的强烈依赖

7. 多个问题参量

1.4.8 处理对于输入的依赖

1.4.9 内存

1.4.10 展望

Q.E.D.