Algorithms, Part I 2-Analysis of Algorithms

2-Analysis of Algorithms

引言

我们为什么要分析算法

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

观察

3-Sum 问题

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

分析暴力算法

image.png

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

Log-log 图

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

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

倍增假说

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

数学模型

简化计算

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

成本模型

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

波浪符号表示

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

image.png

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

image.png

复杂度排序

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

image.png

例:二分查找

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

数学分析

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

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

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

于是:image.png

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

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

算法理论

常用符号

image.png

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

上界

上文已经讨论过,$3-Sum$ 算法不会超过 $N2logN$,即 $O(N2logN)$

下界

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

未解决问题

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

内存消耗

常见内存消耗情况

image.png

总结

经验分析

  • 执行程序

  • 提出运行时间的假设

  • 使用模型进行预测

数学分析

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

科学方法

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