数据结构与算法分析 —— C 语言描述：算法分析

2022-03-16 本文已影响0人 Sun东辉

算法（algorithm）是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。对于一个问题，一旦给定某种算法并且（以某种方式）确定其是正确的，那么重要的一步就是确定该算法将需要多少诸如时间或空间等资源量的问题。如果一个问题的求解算法需要长达一年的时间，那么这种算法就很难有什么用处。

数学基础

四个定义：

如果存在正常数 c 和 $n_0$ 使得当 N≥ $n_0$ 时 T(N)≤ $cf(N)$ ，则记为 T(N) = $O(f(N))$ 。
如果存在正常数 c 和 $n_0$ 使得当 N ≥ $n_0$ 时 T(N) ≥ cg(N)，则记为 T(N) = $\Omega(g(N))$ 。
当且仅当 $T(N) = O(h(N))$ 且 $T(N) = \Omega(h(N))$ 时， $T(N) = \mathrm O(h(N))$ 。
如果 T(N) = O(p(N))且 T(N) ≠ $\mathrm O(p(N))$ ，则 T(N) = o(p(N))。

需要掌握的重要结论：

如果且，那么
- a) $T_1(N) + T_2(N) = max(O(f(N)), O(g(N)))$ 。
- b) $T_1(N) * T_2(N) = O(f(N)*g(N))$ 。
如果 $T(N)$ 是一个 k 次多项式，则 $T(N) = \varnothing(N^k)$ 。
对任意常数 k， $\log^k N = O(N)$ 。它告诉我们对数增长的非常缓慢。

确定两个函数的相对增长率可以使用洛必达法则，该极限可以有四种可能的值：

极限是 0：这意味着 $f(N) = o(g(N))$ 。
极限是 c ≠0：这意味着 $f(N) = \varnothing(g(N))$ 。
极限是 $\infty$ ：这意味着 $g(N) = o(f(N))$ 。
极限摆动：二者无关。

模型

为了在正式的框架中分析算法，我们需要一个计算模型。我们的模型基本上是一台标准的计算机，在机器中顺序地执行指令。该模型有一个标准的简单指令系统，如加法、乘法、比较和赋值等。但不同于实际计算机的情况是，模型机做任意一件简单的工作都恰好话费一个时间单元。

要分析的问题

要分析的的最重要的资源一般就是运行时间。有几个因素影响着程序的运行时间。有些因素（如所使用的编译器和计算机）显然超出了任何理论模型的范畴，因此，虽然它们是重要的，但是我们在这里还不能处理它们。剩下的主要因素则是所使用的算法以及该算法的输入。

通常，输入的大小是主要的考虑问题。我们定义两个函数 $T_{avg}(N)$ 和 $T_{worst}(N)$ ，分别是输入为 N 时算法所花费的平均运行时间和最坏情况下的运行时间。显然， $T_{avg}(N)$ ≤ $T_{worst}(N)$ 。如果存在更多的输入，那么这些函数可以有更多的变量。

一般来说，若无另外的指定，则所需要的量是最坏情况下的运行时间。其原因之一是它对所有的输入提供了一个界限，包括特别坏的输入，而平均情况分析不提供这样的界。另一个原因是平均情况下的界计算起来通常要困难的多。在某些情况下，“平均”的定义可能影响分析结果。

运行时间计算

为了简化分析，我们将采纳如下的约定：不存在特定的时间单元。因此，我们抛弃前导常数。我们还将抛弃低阶顶，从而要做的就是计算大 O 运行时间。由于大 O 是一个上界，因此我们必须仔细，绝不要低估程序的运行时间。实际上，分析的结果为程序在一定时间范围内能够终止运行提供了保障。程序可能提前结束，但绝不可能延后。

一般法则

for 循环：一次 for 循环的运行时间至多是该 for 循环内语句（包括测试）的运行时间乘以迭代的次数。
嵌套的 for 循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的 for 循环的大小的乘积。
顺序语句：将各个语句的运行时间求和即可（这意味着，其中的最大值就是所得的运行时间）。
if / else 语句：一个 if / else 语句的运行时间从不超过判断的时间加上 $S_1$ 和 $S_2$ 中运行时间较长者的总的运行时间。

其他的法则是显而易见的，但是，分析的基本策略是从内部（或最深层部分）向外展开的。如果有函数调用，那么这些调用要首先分析。如果有递归过程，那么存在几种选择。若递归实际上只是稍加掩饰的 for 循环，则分析通常是简单的。

最大子序和

如果数组在磁盘或磁带上，它就可以被顺序读入，在主存中不必存储数组的任何部分。不仅如此，在任意时刻，算法都能对它已经读入的数据给出子序列问题的正确答案（其他算法不具有这个特性），具有这种特性的算法叫做联机算法（on-line algorithm）。仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法。

运行时间中的对数

如果一个算法用常数时间(O(1))将问题的大小消减为其一部分（通常是 1/2），那么该算法就是 O(log N) 的。另一方面，如果使用常数时间只是把问题减少一个常数（如将问题减少 1），那么这种算法就是 O(N) 的。

二分查找：给定一个整数 X 和整数 $A_0$ ， $A_1$ ，...， $A_{N-1}$ ，后者已经预先排序并在内存中，求使得 $A_i = X$ 的下标 $i$ ，如果 X 不在数据中，则返回 $i = -1$ 。
欧几里得算法
- 定理：如果 M > N，则 M mod N < M/2。
幂运算

检验你的分析

一旦完成分析，则需要看一看答案是否正确，是否是最优的。一种实现方法是编程并比较实际观察到的运行时间与通过分析所描述的运行时间是否相匹配。但是，单纯凭实践区分线性程序和 O(N log N)程序是非常困难的。

验证一个程序是 $O(f(N))$ 的另一个常用技巧是对 N 的某个范围（通常用 2 的倍数隔开）计算比值 $\frac{T(N)}{f(N)}$ ，其中 T(N) 是凭经验观察到的运行时间。如果 $f(N)$ 是运行时间的理想近似，那么所算出的值收敛于一个正常数。如果 $f(N)$ 估计过大，则算出的值收敛于 0。如果 $f(N)$ 估计过低从而程序不是 $O(f(N))$ 的，那么算出的值发散。

分析结果的准确性

经验指出，有时分析会估计过大，如果这种情况发生，那么或者需要分析得更细（一般通过机敏的观察），或者可能是平均运行时间显著小于最坏情形的运行时间而又不可能对所得的界再加以改进。对于许多复杂的算法，最坏的界通过某个不良输入是可以达到的，但在实践中它通常是估计过大的。遗憾的是，对于大多数这种问题，平均情形的分析是极其复杂的（在许多情形下还是未解决的），而最坏情形的界尽管有些过分悲观但却是最好的已知解析结果。