2-Analysis of Algorithms

引言

我们为什么要分析算法

• 预测程序性能
• 对比不同算法之间的差异
• 在最坏情况下算法性能的底线
• 了解算法运行的理论基础

观察

3-Sum 问题

给定 N 个不同的数，哪三个数和为零？找出所有这样的三个数。

分析暴力算法

• 可以使用 Java 类 Stopwatch 以分析运行时间情况
• 得到运行时间如图：
• 
• 数据分析

Log-log 图

使用 Log-log 图建立 $lg(T(N))-lgN$ 的函数图像并作线性回归

• 不妨假设 $log(T(N)) = blgN + c$
• 则 $T(N) = 2^{c N}b$
• 
• b = 2.999, c = -33.2103
• 运行时间大约为 $1.006 \times 10^{{-10} \times N}{2.999}$ 秒

倍增假说

• 每次将 N 倍增，测得运行时间
• 运行时间比值取对数得到 $lg \ ratio$ 即大约为 $b$ 的值；确定 b 之后即可确定 a 的值
• 

数学模型

简化计算

图灵和巴贝奇都曾指出，衡量计算复杂程度过程中即便是粗略的标准也是可行的，而且更加方便。

成本模型

使用一些基本的操作来代替运行时间

波浪符号表示

1. 将运行时间或者内存消耗估计为 N 的函数
2. 忽略低阶项

3. 将离散和替代为积分运算可以简化计算过程

复杂度排序

现实世界能够处理的问题规模

例：二分查找

• 目标：给定一个排好序的数组与一个数，找到这个数在数组中的 index
• 实现需要考虑的细节很多：直到 2006 年在 Java Arrays.binarySearch() 的实现中还有 bug！
• 

数学分析

命题：二分查找最多需要 $1+lgN$ 次比较

定义： $T(N)$ 为在长为 $N$ 的有序数组中执行二分查找所需的比较次数

可得：$T(N) \leq T(\frac N 2) + 1,对于N > 1且T(1) = 1$

于是：

例： 3-Sum 的一个 $N^2logN$ 复杂度的算法

1. 对数组排序（$NlogN$）
2. 对于任意的两对数 $a[i]$ 和 $a[j]$，二分查找 $-(a[i] + a[j])$ （$N^2logN$）
3. 故总体复杂度为（$N^2logN$）
4. 已经比暴力 $N^3$ 快很多了
   

算法理论

常用符号

如何分析算法：以 3-Sum 为例

上界

上文已经讨论过，$3-Sum$ 算法不会超过 $N^{2logN$，即 $O(N}2logN)$

下界

至少需要检查 N 项，即 $\Omega(N)$

未解决问题

• 3-SUM 的最佳算法？
• 3-SUM 的小于 $O(N^2)$ 的上界？
• 3-SUM 的大于线性阶的下届？

内存消耗

常见内存消耗情况

总结

经验分析

• 执行程序

• 提出运行时间的假设

• 使用模型进行预测

数学分析

• 分析算法 计算操作的频率
• 使用 ~ 符号来简化分析
• 模型使我们能够解释行为

科学方法

• 数学模型是独立于特定系统的，适用于尚未建成的机器
• 经验分析是验证数学模型和进行预测所必需的

Q.E.D.