Algorithms, Part I 2-Analysis of Algorithms
2-Analysis of Algorithms
引言
我们为什么要分析算法
- 预测程序性能
- 对比不同算法之间的差异
- 在最坏情况下算法性能的底线
- 了解算法运行的理论基础
观察
3-Sum 问题
给定 N 个不同的数,哪三个数和为零?找出所有这样的三个数。
分析暴力算法
- 可以使用 Java 类
Stopwatch
以分析运行时间情况 - 得到运行时间如图:
- 数据分析
Log-log 图
使用 Log-log 图建立 $lg(T(N))-lgN$ 的函数图像并作线性回归
- 不妨假设 $log(T(N)) = blgN + c$
- 则 $T(N) = 2c Nb$
- b = 2.999, c = -33.2103
- 运行时间大约为 $1.006 \times 10{-10} \times N{2.999}$ 秒
倍增假说
- 每次将 N 倍增,测得运行时间
- 运行时间比值取对数得到 $lg \ ratio$ 即大约为 $b$ 的值;确定 b 之后即可确定 a 的值
数学模型
简化计算
图灵和巴贝奇都曾指出,衡量计算复杂程度过程中即便是粗略的标准也是可行的,而且更加方便。
成本模型
使用一些基本的操作来代替运行时间
波浪符号表示
- 将运行时间或者内存消耗估计为 N 的函数
- 忽略低阶项
- 将离散和替代为积分运算可以简化计算过程
复杂度排序
现实世界能够处理的问题规模
例:二分查找
- 目标:给定一个排好序的数组与一个数,找到这个数在数组中的 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$ 复杂度的算法
- 对数组排序($NlogN$)
- 对于任意的两对数 $a[i]$ 和 $a[j]$,二分查找 $-(a[i] + a[j])$ ($N^2logN$)
- 故总体复杂度为($N^2logN$)
- 已经比暴力 $N^3$ 快很多了
算法理论
常用符号
如何分析算法:以 3-Sum 为例
上界
上文已经讨论过,$3-Sum$ 算法不会超过 $N2logN$,即 $O(N2logN)$
下界
至少需要检查 N 项,即 $\Omega(N)$
未解决问题
- 3-SUM 的最佳算法?
- 3-SUM 的小于 $O(N^2)$ 的上界?
- 3-SUM 的大于线性阶的下届?
内存消耗
常见内存消耗情况
总结
经验分析
-
执行程序
-
提出运行时间的假设
-
使用模型进行预测
数学分析
- 分析算法 计算操作的频率
- 使用
~
符号来简化分析 - 模型使我们能够解释行为
科学方法
- 数学模型是独立于特定系统的,适用于尚未建成的机器
- 经验分析是验证数学模型和进行预测所必需的