算法/导论

顶部，章节：1，2，3，4，5，6，7，8，9，A

本书涵盖了算法设计和分析的技术。涵盖的算法技术包括：分治法、回溯法、动态规划、贪心算法和爬山法。

任何可解问题通常至少有一种以下类型的算法

显而易见的方式；
有条理的方式；
巧妙的方式；并且
神奇的方式。

在第一个也是最基本的层面上，“显而易见”的解决方案可能会尝试穷举搜索答案。直观地说，如果您熟悉编程语言和基本问题解决技术，显而易见的解决方案是易于想到的解决方案。

第二个级别是有条理的级别，也是本书的核心：在理解此处介绍的材料后，您应该能够有条理地将大多数显而易见的算法转变为性能更好的算法。

第三级，巧妙的级别，需要更多地了解问题中涉及的元素及其属性，甚至需要重新制定算法（例如，数值算法利用了不明显的数学属性）。一个巧妙的算法可能难以理解，因为它不明显它是正确的，或者可能难以理解它实际上比它看起来需要的运行速度更快。

算法解决方案的第四个也是最后一个级别是神奇的级别：这保留了在突破导致高度非直观的解决方案的罕见情况下。

当然，所有这四个级别都是相对的，除了有条理的技术外，本书还涵盖了一些巧妙的算法。让我们开始吧。

先决条件

要理解本书中介绍的材料，您需要足够了解一门编程语言，以便将本书中的伪代码转换为有效的解决方案。您还需要了解以下数据结构的基础知识：数组、堆栈、队列、链表、树、堆（也称为优先级队列）、不相交集和图。

此外，您应该了解一些基本算法，如二分查找、排序算法（归并排序、堆排序、插入排序或其他算法），以及广度优先搜索或深度优先搜索。

如果您不熟悉这些先决条件中的任何一个，您应该首先复习数据结构一书中的材料。

什么时候效率很重要？

并非每个问题都需要最有效的解决方案。就我们而言，术语效率与执行任务所需的时间和/或空间有关。当时间或空间充足且便宜时，可能不值得让程序员花一两天时间来使程序更快。

但是，以下是一些效率很重要的案例

当资源有限时，算法的改变可以节省大量成本，并允许有限的机器（如手机、嵌入式系统和传感器网络）扩展到可能的极限。

当数据量很大时，更有效的解决方案可能意味着任务在两天内完成与两周内完成之间的区别。示例包括物理学、遗传学、网络搜索、大型在线商店和网络流量分析。

实时应用程序：术语“实时应用程序”实际上是指提供时间保证的计算，而不是“快速”。但是，通过选择合适的算法，可以进一步提高质量。

计算量大的工作，如流体动力学、偏微分方程、VLSI 设计和密码分析，有时只有在找到足够有效的解决方案时才能考虑。

当子程序是通用的并且经常使用时，在更有效的实现上花费的时间可以为使用该子程序的每个应用程序带来好处。示例包括排序、搜索、伪随机数生成、内核操作（不要与操作系统内核混淆）、数据库查询和图形。

简而言之，当您没有时间时，节省时间很重要。

什么时候效率不重要？这些案例的示例包括仅使用几次的原型、输入量很小的案例、简单性和易于维护比效率更重要的案例、所关注的区域不是瓶颈，或者代码中其他过程或区域将从高效的设计和对算法的关注中获得更多好处。

发明算法

因为我们假设您了解某种编程语言，所以让我们从如何将想法转化为算法开始。假设您想编写一个函数，该函数将以字符串作为输入，并以小写形式输出字符串

// tolower -- translates all alphabetic, uppercase characters in str to lowercase
function tolower(string str): string

当您想到解决这个问题时，您首先想到的是什么？也许您脑海中浮现了这两个考虑因素

需要查看str 中的每个字符
需要将单个字符转换为小写例程

第一点是“显而易见”的，因为需要转换的字符可能出现在字符串中的任何位置。第二点是从第一点得出的，因为一旦我们考虑了每个字符，我们就需要对其执行某些操作。有许多方法可以编写字符的tolower函数

function tolower(character c): character

有几种方法可以实现此函数，包括

在表中查找c——一个字符索引数组，其中包含每个字符的小写版本。

检查c 是否在范围 'A' ≤ c ≤ 'Z' 内，然后向其添加数值偏移量。

这些技术取决于字符编码。（作为关注点分离问题，也许表格解决方案更强大，因为它更清楚地表明您只需要更改代码的一部分。）

但是，无论以何种方式实现此子例程，一旦我们拥有它，我们原始问题的实现就会立即出现

// tolower -- translates all alphabetic, uppercase characters in str to lowercase
function tolower(string str): string
  let result := ""
  for-each c in str:
    result.append(tolower(c))
  repeat
  return result
end

此代码示例也可在Ada 中获得。

循环是我们能够将“需要查看每个字符”转换为我们的原生编程语言的结果。显而易见的是，tolower 子程序调用应该在循环主体中。将高级任务转换为实现所需的最后一步是决定如何构建生成的字符串。在这里，我们选择从空字符串开始，并将字符追加到它的末尾。

现在假设您想编写一个用于比较两个字符串的函数，该函数测试它们是否相等，忽略大小写

// equal-ignore-case -- returns true if s and t are equal, ignoring case
function equal-ignore-case(string s, string t): boolean

这些想法可能会出现在您的脑海中

字符串s 和t 中的每个字符都必须查看
一个遍历两者的单循环可以实现这一点
但这样的循环应该首先小心字符串长度是否相等
如果字符串长度不同，则它们不可能相等，因为忽略大小写并不影响字符串的长度
可以再次使用字符的 tolower 子程序，并且只比较小写版本

这些想法来自您对字符串以及语言中循环和条件构造的熟悉程度。您想到的函数可能类似于以下函数

// equal-ignore-case -- returns true if s or t are equal, ignoring case
function equal-ignore-case(string s[1..n], string t[1..m]): boolean
  if n != m:
    return false               \if they aren't the same length, they aren't equal\
  fi
  
  for i := 1 to n:
    if tolower(s[i]) != tolower(t[i]):
      return false
    fi
  repeat
  return true
end

此代码示例也可在Ada 中获得。

或者，如果您从函数分解而不是迭代的角度考虑问题，您可能想到的函数更像这样

// equal-ignore-case -- returns true if s or t are equal, ignoring case
function equal-ignore-case(string s, string t): boolean
  return tolower(s).equals(tolower(t))
end

或者，您可能觉得这两个解决方案都不够有效，并且您更喜欢只对s 或t 进行一次遍历的算法。以上两个实现都需要两次遍历：第一个版本计算长度，然后比较每个字符，而第二个版本计算字符串的小写版本，然后将结果彼此比较。（请注意，对于一对字符串，也可以预先计算长度以避免第二次遍历，但这有时会有其自身的缺点。）您可以想象如何编写类似的例程来测试字符串相等性，这些例程不仅忽略大小写，还忽略重音符号。

你现在可能已经开始理解本书中的伪代码了。伪代码语言并非真正的编程语言：它抽象掉了你必须在任何语言中都要处理的细节。例如，该语言不假设泛型或动态类型与静态类型：它的理念是应该明确意图，并且将其转换为你的母语不应该太难。（但是，在这样做的过程中，你可能需要做出一些设计决策，将实现限制为一种特定的类型或数据形式。）

到目前为止，我们用来解决这些简单字符串问题的技术没有什么特别的：这些技术可能已经在你的工具箱里了，你可能已经找到了在你选择的编程语言中表达这些解决方案的更好或更优雅的方法。在本书中，我们将探索更通用的算法技术，以进一步扩展你的工具箱。将一个简单的算法改进成更高效的算法可能并不那么容易，但通过理解本书中的内容，你应该能够有条不紊地应用不同的解决方案，最重要的是，你将能够对自己程序提出更多问题。提问与回答一样重要，因为提出正确的问题可以帮助你重新表述问题，跳出框框思考。

理解算法

计算机程序员需要具备出色的多层抽象推理能力。例如，考虑以下代码

function foo(integer a):
  if (a / 2) * 2 == a:
     print "The value " a " is even."
  fi
end

要理解这个例子，你需要知道整数除法使用截断，因此当 if 条件为真时，a 中的最低有效位为零（这意味着 a 必须为偶数）。此外，代码使用字符串打印 API，它本身是一个由不同模块使用的函数的定义。根据编程任务，你可能需要考虑硬件层，一直到处理器分支预测或缓存级别。

二进制的理解通常至关重要，但许多现代语言的抽象已经远离“硬件”，因此这些较低级别并不必要。抽象在某个地方停止：大多数程序员不需要考虑逻辑门，电子物理也不必要。然而，多层思考是编程中必不可少的一部分。

但是，从计算机程序转向算法需要另一层：数学。一个程序可能利用二进制表示的特性。一个算法可以利用集合论或其他数学构造的特性。正如二进制本身在程序中并不显式一样，算法中使用的数学属性也是不显式的。

通常，当介绍一种算法时，需要进行讨论（与代码分离）来解释该算法使用的数学方法。例如，要真正理解贪心算法（如 Dijkstra 算法），你应该理解数学性质，这些性质表明贪心策略在所有情况下都是有效的。在某种程度上，你可以将数学视为算法调用的自身的一种子程序。但这种“子程序”在代码中不存在，因为没有可调用的东西。当你阅读本书时，尝试将数学视为一个隐式子程序。

技术的概述

本书涵盖的技术在以下概述中突出显示。

分治：许多问题，特别是当输入以数组的形式给出时，可以通过将问题分解成更小的部分（分）、递归地解决这些较小的部分（治），然后将这些解决方案合并成单个结果来解决。例如，归并排序和快速排序算法。

随机化：越来越多的随机化技术对于许多应用程序至关重要。本章介绍了一些使用随机数的经典算法。

回溯：几乎任何问题都可以以某种形式表示为回溯算法。在回溯中，你考虑所有可能的解决方案，并在假设已做出选择的情况下递归地解决子问题。递归调用的集合生成一棵树，其中树中的每个选择集合都会被依次考虑。因此，如果存在解决方案，它最终会被找到。

回溯通常是一种低效的蛮力技术，但有一些优化措施可以执行，以减少树的深度和分支的数量。该技术被称为回溯，因为在访问树的一个叶子节点之后，算法将返回到调用堆栈（撤销没有导致成功的选择），然后继续沿着其他分支进行。要使用回溯技术解决问题，问题需要具有一定形式的“自相似性”，即问题（在做出选择之后）的较小实例必须类似于原始问题。通常，问题可以概括为自相似的。

动态规划：动态规划是针对回溯算法的优化技术。当子问题需要重复解决时（即，当回溯算法中存在许多重复分支时），通过首先解决所有子问题（自下而上，从小到大）并将每个子问题的解决方案存储在一个表中，可以节省时间。因此，每个子问题只访问和解决一次，而不是重复解决。“规划”一词来自在表中记录内容的意义；例如，电视节目编排是指在表中记录哪些节目将在何时播出。

贪心算法：当对可能的选项有足够的了解，从而可以在不考虑所有可能选项的情况下确定“最佳”选项时，贪心算法非常有用。通常，贪心算法并不难写，但很难证明其正确性。

爬山算法：我们探索的最后一种技术是爬山算法。基本思路是从问题的糟糕解决方案开始，然后反复应用优化，直到找到最佳解决方案或满足其他要求。爬山算法的一个重要案例是网络流。尽管名称如此，但网络流对于描述关系的许多问题都有用，因此不仅仅用于计算机网络。许多匹配问题可以使用网络流来解决。

顶部，章节：1，2，3，4，5，6，7，8，9，A

算法和代码示例

一级（最简单）

1. 查找最大值 包含算法和多种不同的编程语言

2. 查找最小值 包含算法和多种不同的编程语言

3. 查找平均值 包含算法和多种不同的编程语言

4. 查找众数 包含算法和多种不同的编程语言

5. 查找总和 包含算法和多种不同的编程语言

6. 计数包含算法和多种不同的编程语言

7. 查找平均值包含算法和多种不同的编程语言

二级

1. 与计算机对话一级 包含算法和多种不同的编程语言

2. 排序 - 冒泡排序 包含算法和多种不同的编程语言

三级

1. 与计算机对话二级 包含算法和多种不同的编程语言

四级

1. 与计算机对话三级 包含算法和多种不同的编程语言

2. 查找近似最大值 包含算法和多种不同的编程语言

五级

1. 快速排序