算法算法分析

基于随机访问机模型分析算法

字数统计: 1.4k字   |   阅读时长: 5分

摘要: 分析算法的方法论

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

分析算法，也就是预测算法需要的时间和资源。我们关心的资源问题包括内存、通信带宽、计算机硬件等。但我们往往更关心时间问题。

算法的时间跟算法的实现是有关系的，因此在分析算法之前，需要明确实现技术的模型，包括描述所用资源及其代价的模型。本文我们考虑一种通用的单处理器计算模型：随机访问机（Random Access Machine, RAM）作为实现技术。在 RAM 模型中，指令一条接一条执行，没有并发操作。

RAM 模型的设计

指令

RAM 模型的指令及其代价需要事先定义，为了贴合实际，真实的计算机的指令是如何设计的，RAM 就如何设计。

RAM 模型包含真实计算机常见的指令，每条指令所需时间为常量：

  • 算术指令：加法、减法、乘法、出发、取余、上取整、下取整。
  • 数据移动指令：装入、存储、复制
  • 控制指令：条件转移、无条件转移、子程序调用和返回

数据

RAM 模型的数据类型包括整数和浮点数，同时对每个数据字的规模限定一个范围，比如当处理规模为 $n$ 的输入时，对于常量 $c \geq 1$，整数由 $c\log{n}$ 位表示。

灰色区域

真实计算机包含一些上面未列出的指令，这些指令代表 RAM 模型的一个灰色区域。例如指数运算是一条常量时间指令吗，一般情况下不是，但当 $k$ 不大于一个计算机字中的位数，就可以用一条常量时间指令来计算 $2^{k}$，也就是左移 $k$ 位。

内存层次

在 RAM 模型中，我们不对计算机中常见的内存层次建模，比如高速缓存、虚拟内存等。实际运行程序时，内存层次有时对时间的影响很大，但分析算法时不考虑这些影响。

分析程序运行时间

通常把一个程序的运行时间描述为输入规模的函数。

输入规模

输入规模怎样定义，依赖于研究的问题，比如排序的输入规模是输入中的项数；两个整数相乘，输入规模是二进制表示输入所需的总位数；若算法输入是图，则输入规模可以用顶点数和边数的数对描述。

运行时间

算法在特定输入上的运行时间指执行的基本操作数，在 RAM 观点下，伪代码中的第 i 行每次执行需要常数时间 $c_{i}$。

例子：插入排序

首先给出插入排序算法的伪代码：

1
2
3
4
5
6
7
8
9
Insertion-Sort(A)                                       代价  次数
for j = 2 to A.length:                                  c1    n
    key = A[j]                                          c2    n-1
    // insert A[j] into the sorted sequence A[1..j-1]   0     n-1
    i = j - 1                                           c4    n-1
    while i > 0 and A[i] > key                          c5    t2+t3...+tn
        A[i + 1] = A[i]                                 c6    (t2-1)+(t3-1)+...+(tn-1)
        i = i - 1                                       c7    (t2-1)+(t3-1)+...+(tn-1)
    A[i + 1] = key                                      c8    n-1

其中 $t_{j}$ 表示对 j，第 5 行执行 while 循环的次数。

然后分析伪代码中每行的执行时间和执行次数。

为了计算在 n 个值的输入上插入排序算法的运行时间 $T(n)$，对代价和次数对应的乘积求和即可：

给定规模下的具体输入对算法运行时间的影响

最好情况

如果输入数组已经排好序，则对 $j=2,3,\cdots,n$，有 $t_{j} = 1$：

最坏情况

若输入已经反向排序，则对 $j=2,3,\cdots,n$，有 $t_{j} = j$，于是：

平均情况

随机选择 n 个数并应用插入排序。平均来说 [A1..j-1] 中一半元素小于 A[j]，一半元素大于 A[j]，所以需要检查 A[1..j-1] 的一半来确定插入 A[j] 的位置，于是 $t_{j} = \frac{1}{2}$。

一般情况下我们对最坏情况该兴趣，一方面因为平均情况很多时候与最坏情况的运行时间一样，比如插入排序就是这样，都是输入规模的二次函数。另一方面平均情况分析范围有限，需要假定给定规模的所有输入有相同的可能性，而这个假定可能不成立。

有时使用随机化算法，用概率分析并给出期望运行时间就会比较有用。

Share