算法分析导论

引言

算法 是解决问题的过程或过程描述。算法是为计算输出、处理数据或执行功能而要执行的操作的逐步规范。算法必须始终是正确的（它必须始终产生有效的输出），并且它必须是有限的（它必须在有限的步骤后终止）。

算法不是代码。特定语言的程序和代码是算法的 实现。“算法”这个词本身源自波斯数学家 Abu ‘Muhammad ibn Musa al-Khwarizmi（约 780 – 850）的拉丁化。算法的概念比现代计算机早了几千年。欧几里得计算最大公约数的算法已有 2,300 年的历史。

通常，为了有用，算法还必须是 可行的：给定其输入，它必须使用合理的资源量在合理的时间内执行。根据应用要求，我们的容忍度可能在几毫秒到几天之间。执行需要数年或数世纪的算法当然不被认为是可行的。

确定性 如果给定特定的输入，算法总是经历完全相同的计算过程并产生相同的输出，则该算法是确定性的。到目前为止，您使用的大多数算法都是确定性的。

随机 随机算法是涉及某种形式的随机输入的算法。随机源可用于做出决策（例如随机选择）或在程序中生成随机状态作为候选解决方案。随机算法有很多类型，包括拉斯维加斯算法（其结果总是正确的，但可能会以一定的概率失败而不产生任何结果）等。

优化 许多算法不仅寻求寻找问题的解决方案，而且寻求寻找 最佳、最优的解决方案。许多此类算法是 启发式 的：它们不是寻找实际的最佳解决方案（这可能是不可行的），而是可以逼近解决方案（近似 算法）。其他算法模拟生物过程（遗传算法、蚁群算法等）来搜索最优解。

并行 大多数现代处理器都是多核的，这意味着它们在一个芯片上有多个处理器。许多服务器有数十个共同工作的处理器。可以通过设计并行算法来利用多个处理器，这些算法可以将工作拆分到多个进程或线程中，这些进程或线程可以相互并行执行，从而提高整体性能

分布式 计算也可以分布在可能位于半个地球之外的完全独立的设备之间。已经建立了大规模分布式计算网络用于研究，例如模拟蛋白质折叠 (Folding@Home)。

算法是您在典型编程语言中可能习惯使用的东西的更抽象、更通用的概念。在实际程序中，您可能有函数/方法、子程序或过程等。这些代码片断中的每一个本身都可以被认为是一个算法。这些较小部分的组合创建了更复杂的算法，等等。程序本质上是更通用、理论算法的具体实现。

当程序执行时，它会消耗一定数量的资源。例如：

时间 算法消耗的最明显的资源是时间：算法完成其计算需要多长时间（以秒、分钟等为单位衡量）。或者，时间可以用特定硬件执行算法需要多少个 CPU 周期或浮点运算来衡量。

内存 y 计算机中的第二个主要资源是内存。算法需要内存来存储输入、输出，并且在执行期间可能需要额外的内存。在某些内存极度受限的环境或系统（例如嵌入式系统）中，算法在执行中使用多少内存甚至可能比时间更重要。

功耗 当您拥有有限的容量（例如移动设备中的电池）时，设备消耗的电量是一个重要的考虑因素。从消费者的角度来看，运行速度较慢但电池寿命是其两倍的手机可能更可取。在无线传感器网络或自治系统等某些应用中，功耗可能比时间或内存更重要。

带宽 在计算机网络中，效率是通过您可以从一台计算机传输到另一台计算机的数据量来衡量的，称为吞吐量。吞吐量通常受到网络带宽的限制：网络连接在理想情况下（无数据丢失、无重传等）可以传输多少数据

电路 在设计硬件时，资源通常通过实现硬件所需的门或线的数量来衡量。更少的门和线意味着您可以在硅片上放置更多的芯片，从而导致更便宜的硬件。更少的线和门也意味着更快的处理。

空闲 即使计算机没有计算任何东西，它仍然可以“花费”您一些东西。考虑购买运行一个针对小型用户群的 Web 服务器的硬件。在硬件上有实质性的投资，它需要维护，最终必须更换。然而，由于用户群很小，大多数时间它都处于空闲状态，消耗功耗。一个更好的解决方案可能是使用相同的硬件来服务多个虚拟机 (VM)。现在可以使用相同的硬件为几个小型 Web 服务器提供服务，从而提高我们的硬件利用率。在这样的场景中，缺乏正在执行的工作就是资源。

负载 在某种程度上与空闲相反，有时应用或服务可能会偶尔出现高需求时期。系统服务此类高负载的能力可以被视为一种资源，即使处理它们的能力在大多数时间未被使用。

这些都是在设计系统、代码和算法时非常重要的工程和业务考虑因素。然而，我们希望以更抽象的方式考虑算法的复杂性。

假设我们有两个不同的程序（或算法）A 和 B。这两个算法都是正确的，但 A 比 B 使用更少的上述资源。显然，算法 A 是更好的、更有效的解决方案。然而，我们如何更好地量化这种效率？

列表操作

为了给出一个具体的例子，考虑一个典型的列表 ADT。列表可以实现为基于数组的列表（其中类拥有一个在变满时重新调整大小/复制的静态数组）或链表（具有包含元素并链接到列表中下一个节点的节点）。某些操作在一种类型的列表上是“便宜”的，而其他操作可能会更“昂贵”。

考虑在开头（索引 0）将一个新元素插入列表的问题。对于链表，这涉及创建一个新节点并重新排列几个引用。这种情况下的操作次数不取决于列表的 大小。相比之下，对于基于数组的列表，如果列表包含 n 个元素，则每个元素将需要在数组中 移位 一个位置，以便为要插入的元素腾出空间。移位次数与数组中的元素数量 n 成正比。显然，对于这个操作，链表更好（更高效）。

现在考虑一个不同的操作：给定一个索引 i，检索列表中的第 i 个元素。对于基于数组的列表，我们拥有对数组随机访问的优势。当我们索引一个元素 arr[i] 时，只需一次内存地址计算即可“跳转”到包含第 i 个元素的内存位置。相比之下，这里，链表将需要我们从头开始，并遍历列表直到达到第 i 个节点。这需要 i 次遍历操作。在最坏的情况下，检索最后一个元素（第 n 个元素）将需要 n 次此类操作。这些操作的总结可以在表 2.1 中找到。

列表类型	在开头插入	基于索引的检索
基于数组的列表	n	1
链表	2	i ≈ n

表 2.1: 列表操作复杂性总结

我们已经对基于我们选择的数据结构类型的算法的相对性能有了很好的理解。在这个例子中，我们看到了常数时间算法和线性算法。常数时间算法执行常数数量的操作，而不管输入的大小（在这种情况下，列表的大小 n）。线性算法执行的操作次数与输入的大小线性相关。
在接下来的例子中，我们将开始对这种类型的分析进行一点更正式的说明。