计算机科学基础/算法复杂度

算法复杂度

“算法是抽象的配方，规定了可能由人类、计算机或其他方式执行的过程。因此，它代表了一个非常通用的概念，有许多应用。”——大卫·哈雷尔，“算法——计算的精神”。

我们已经了解到算法是问题的概念解决方案。计算算法可以用计算机可以执行的通用工作单元来描述/定义，这样它们就与编程语言和执行环境（计算机）无关。算法编写是一个创造性的过程，正如弗朗西斯·沙利文所说：“对我来说，伟大的算法是计算的诗歌。就像诗歌一样，它们可以是简短的、含蓄的、密集的，甚至神秘的。但一旦解开，它们就会为计算的某些方面投下新的光彩。”您已经看到了使用伪代码和流程图等抽象符号记录的示例算法。

一旦算法被实现/编码，即被具体的符号表示，它们就会在体现它们的程序中变得活跃起来。程序可以由计算机执行/运行。能够运行不同的程序来实现各种算法是计算机作为机器的独特功能。通常，当我们购买一台机器时，例如家用电器，我们假设它具有一组定义明确的功能。例如，微波炉应该加热和烹饪我们的食物，仅此而已。我们不希望微波炉能够为我们洗衣服。计算机器（计算机）则不同。我们希望它执行任何程序使其执行的功能——计算机的功能是可扩展的。如果我们将计算机比作汽车，程序员就是可以使汽车做不同事情的司机（在一定程度上），而用户就像乘坐汽车享受功能的乘客。这也是每个人都需要学习计算机编程的原因，因为它赋予你让计算机做不同事情的自由。

算法的正确性

算法必须正确才能有用。我们必须仔细检查我们的算法，以消除错误，然后再使用它们创建程序。如果算法有错误，则无法创建正确的程序。我们经常提醒学生，如果他们的算法在纸上不起作用，它们在计算机上也无法起作用。因此，我们必须首先在纸上找出我们的算法。

即使算法的设计是正确的，我们也可能在编程过程中引入错误。像任何自然语言一样，编程语言也有自己的语法，包括使用该语言的语法规则。当我们违反这些规则时，就会在程序中引入语法错误。这种类型的错误很容易修复，事实上，大多数现代程序编辑器可以检测到此类错误并提醒我们。另一种类型的错误是逻辑错误，这是由于语言使用不当造成的。换句话说，我们语法正确的程序对计算机没有意义或没有意义。例如，食谱即使所有句子都语法正确，也可能不清楚或具有误导性。你可能认为计算机在运行逻辑错误的程序时也会出错。这是真的，但这种情况很少见，尤其是在配备了错误检测机制的现代计算机中。我们通常假设计算机不会出错。如果程序没有生成正确的结果，那就是人为错误的结果。

我们也称逻辑错误为软件错误。最初的“错误”实际上是一个硬件故障——一只飞蛾卡在机电计算机中。现在，错误通常用于指代计算机系统中的任何错误/故障，包括硬件和软件。当计算机程序有错误时，它会产生错误的结果或崩溃，因为计算机可能不知道下一步该做什么。另一个更微妙的错误可能会导致计算机程序永远无法完成，被称为无限循环，这显然不是我们想要的。

错误几乎是不可避免的，因为人类会犯错误。那么，我们如何修复错误以确保程序的正确性呢？我们必须测试我们的程序以验证其正确性。测试包括程序的样本输入和程序的预期输出。我们可以通过对程序进行样本输入并收集实际输出来运行测试。如果实际输出与预期输出匹配，则程序通过测试，否则程序或测试中存在错误（测试也可能出错）。我们通常使用一组测试（测试套件）来测试算法的不同部分。这个过程被称为调试，如以下伪代码所示

for each test in the test suite
  run and compare the actual output to the desired output
  if they match move on to the next test
  otherwise fix the bug and repeat the whole process

请注意，除了非常简单的程序外，很难使我们的测试详尽无遗。当程序变得更大更复杂时，覆盖所有可能情况所需的测试数量会迅速增加。正如戴克斯特拉所说，“程序测试可以用来证明存在错误，但不能用来证明不存在错误！”有一些技术可以证明程序的正确性。例如，计算机处理器的微代码通常通过形式验证来证明其正确性。

算法的“优劣”

通常总有多种方法可以解决同一个问题，因此，也有多种算法可以使计算机为我们解决问题。除了正确地解决问题外，我们还希望能够比较/评估解决同一个问题的算法。我们必须定义算法设计中“优劣”的标准/度量。这些标准或度量可以包括简单性、易于实现性、执行速度或答案的精确性。在计算中，我们最关心的是解决方案速度，因为快速的算法可以在相同的时间内解决更大的问题或更多的问题。这也称为效率——对许多过程的经济衡量。通常，许多程序的有用性取决于结果的及时性。例如，一个需要 24 小时才能预测第二天天气的程序几乎没有用。

给定一个算法，我们如何衡量它的“速度”？一种可能的方法是实现算法，运行结果程序，并测量其执行时间——程序运行开始和结束之间经过的时间。这种方法存在一些挑战。首先必须实现算法，这可能是一项艰巨的任务。其次，要运行两个程序来比较它们的执行时间，我们必须对它们进行相同的输入（也称为工作负载，例如要排序的百万个数字列表），并且输入的大小永远不理想。第三，运行程序的“速度”受执行环境的影响，例如机器的硬件配置。以食谱为例。不同的厨师肯定需要不同的时间来完成它。需要的食物数量肯定会放大差异——随着我们增加配料的数量，冗长的食谱需要更长的时间来完成。但是，食谱中有一些内在特性会影响准备时间。如果食谱包含打鸡蛋，可以指导厨师将每个鸡蛋打碎并单独搅拌，或者先将所有鸡蛋打碎在一起搅拌。显然，第一种方法由于涉及的步骤更多而更慢。计算中的算法表现出类似的特征。回想一下，算法必须用计算机可以执行的工作单元（步骤）来定义，以便它可以直接在编程语言中实现。算法中步骤的排序和组织方式会显着影响实现算法的程序的执行时间。

由于算法是解决问题的概念性方案，我们希望在抽象意义上研究它们的“速度”，而无需实际实现它们。这在计算机科学中被称为算法分析。在这种方法中，我们采用用伪代码或流程图描述的算法，计算步骤数量（工作单位），这始终是输入大小的函数。在上述食谱示例中，遵循第一种方法（分别打破每个鸡蛋并将其搅拌）所需的时间与所涉及的鸡蛋数量成正比。事实上，如果只需要一个鸡蛋，两种方法之间没有区别。我们不测量针对特定输入大小所采取的步骤，而是关注步骤数量和输入大小之间的关系函数，这显示了工作量（成本）随着输入大小增加而增长的模式。这样的函数也称为增长函数。然后，我们应用渐近分析，它将函数比较为输入接近无穷大，以简化函数，因为随着输入大小接近无穷大，工作单位之间的差异消失（我们可以假设打破鸡蛋和搅拌鸡蛋所花费的时间相同），并且任务中最“复杂”部分的成本将占主导地位（重复步骤 10 次的部分将超过只执行一次的任何步骤）总成本。例如，在一个食谱中，我们有一个快速步骤（每份服务 0.0001 秒）重复 10 次，而一个慢速步骤（每份服务 10 秒）不重复，N 份服务量（输入大小）将花费 $0.0001*10*N$ 在重复步骤上总共花费秒，并且始终在慢速步骤上花费 10 秒。当 N 大于 10000 时，重复部分的成本将超过慢速部分的成本。在渐近分析中，我们可以忽略慢速步骤，因为当 N 接近无穷大时，它对总成本的贡献可以忽略不计。通过简化的增长函数，我们可以将它们归类，并认为每个类别的算法具有相似的性能特征。这种分析并不完全精确，但它在研究算法的性质和预测其性能方面非常有用。我们学习如何将算法归类，并根据它们所属的类别对其性能进行排名。我们使用大 O 符号表示每个类别。

总之，我们讨论了以下几个关于算法复杂度分析的关键概念

算法是解决问题的概念抽象方案，程序是计算机可以运行的具体可执行代码。我们不能在计算机上运行算法；我们只能运行实现算法的程序。因此，算法的性能在定义上是抽象的（不能具体定义或测量）。
算法的优劣度量必须是算法本身的内在特征——反映设计“巧妙性”的东西，而与实现细节和未来的执行环境无关。
从经济角度来看，我们关心算法的时间和空间成本。在本课程中，我们将只关注时间成本。我们不能实际测量算法的时间成本，但我们可以研究时间成本和输入大小之间的关系，这反映了算法的内部复杂度（或巧妙性）。我们将这种关系表示为增长函数，其中输入大小为变量，总成本为值。通过仅保留支配项（渐近分析）可以简化增长函数，因为当输入变得非常大（最终接近无穷大）时，其他项无关紧要。简化的增长函数被归类，算法可以根据它们所属的类别进行排名。
当输入大小足够大时，低复杂度类别的算法将比高复杂度类别的算法性能更好。我们关心大型输入大小，因为任何算法都可以快速解决小问题。使用这种算法分析技术，我们可以评估和比较算法，以预测在实际实现任何算法之前实现这些算法的程序的相对性能。
效率，作为另一个经常使用的术语，与复杂度成反比。更复杂的算法效率更低，因为它通过变得更复杂而对计算资源的利用效率更低。

示例

至少有两种方法可以计算 1 到 N 之间所有数字的总和。以下是两种算法

算法 1：手动逐个添加所有数字
算法 2：使用此公式计算结果 $(N+1)*(N/2)$

考虑以下问题：如果我们手动执行这两种算法，哪一种运行速度更快，如果

N = 2？
N = 100？
N = 1,000,000？

让我们看看算法在计算机上的表现（实现后）。以下脚本使用一个块来实现算法 1，该块迭代遍历范围内的所有数字并将它们逐个添加到总和中。

一个 Snap! 脚本，用于添加两个数字之间的所有数字。

可以使用算法 2 解决相同的问题，该算法使用函数来计算结果，如以下脚本和报告块所示。

一个 Snap! 报告块，用于计算范围内所有数字的总和并报告结果。

一个 Snap! 块，用于计算范围内所有数字的总和。

两个脚本（程序）都采用相同的输入——定义范围的两个数字。范围内的数字数量是输入大小，或者更确切地说，是问题大小。我们假设工作单位是算术运算 $+-*/$ 、赋值操作和报告操作。这样的假设是合理的，因为实际上这些操作花费的时间相同，而与操作数无关。如果您运行这些程序并尝试不同的输入大小，您将观察到，随着您增加输入大小，第一个程序的执行时间稳步增加，而第二个程序的执行时间没有变化。我们能预测这种行为吗？

让我们将算法分析应用于这两个算法。第一个算法循环遍历数字以获取总和，因此成本（步骤数 - 加法）和输入大小之间的关系函数为 $f=a+b*N$ ，假设 N 是输入大小，a 和 b 是创建脚本变量的成本和加法的成本。请注意，a 和 b 都是常数，因为它们对于给定的计算机不会改变。我们可以将函数简化为 $f=N$ ，因为当 N 接近无穷大时，常数不再重要。我们将具有这种增长函数类型的算法分配到更精简的算法类别，这种函数称为线性时间，用 $O(N)$ 表示。第二个算法始终花费相同的时间，因为它执行的运算集与输入大小无关。它属于常数时间类别，用 $O(1)$ 表示。

让我们考虑另一个问题：列表中的数字是否不同？以下是在伪代码中描述的直接算法。

步骤 1：将第一个数字与列表中的所有其他数字进行比较。如果在任何时候看到相同的数字，停止并回答否。
步骤 2：通过从列表中获取下一个数字并将其与所有其他数字进行比较来重复步骤 1。
步骤 3：使用完列表中的所有数字后，停止并回答是。

输入大小是列表的大小。列表中的数字越多，回答问题所需的时间就越长。根据算法，第一个比较可能会发现两个相同的数字，从而立即回答问题。这是一个好的设计，因为在这一点上，没有必要继续执行算法的其余部分。当我们分析算法时，我们专注于最坏情况，因为算法的性能取决于实际输入，我们不应该依赖运气！因此，对于该算法，成本和输入大小之间的关系（增长）函数应该是 $f=N*(N-1)$ ，因为在最坏情况下（所有数字都是唯一的），算法必须将每个数字与列表中的所有其他数字进行比较，然后才能得出答案。为了简化函数，只保留最大的主导项，我们得到 $f=N^{2}$ ，这将该算法置于二次类别 $O(N^{2})$ 中。如果您有兴趣，可以复制并运行以下脚本（算法的实现），以验证算法的预测性能特征。

让我们看看另一个类别的算法：打印所有 n 位数字？

For each number in 0, 1, 2, 3, ..., 9 
 use the number for the first digit
 enumerate all n-1 digit numbers
 append each every n-1 digit number to the first digit to form a n digit number

这个例子有点牵强，但它演示了一个新的性能类别，在我们讨论加密技术时非常有用。该算法很复杂，仅仅是因为它必须生成的输出（所有 n 位数字）数量很多。因此，输出部分的成本将占总成本的绝大部分。为了生成所有 n 位数字，我们必须首先生成所有 n-1 位数字。为了生成所有 n-1 位数字，我们必须首先生成所有 n-2 位数字，依此类推。从后向前研究该过程更容易。假设输出一个数字是工作单位（输出一个数字所需的时间相同），生成所有一位数字的成本为 10。为了生成所有两位数字，我们必须输出 $10*10=10^{2}$ 个数字。对于三位数字，成本为 $10^{3}$ 。您看到模式了吗？为了生成所有 n 位数字，成本为 $10^{n}$ 。这种类型的算法比二次算法快得多，因为输入大小在指数中。它们属于指数时间类别，用 $O(2^{N})$ 表示。根（在本例中为 2）并不重要。因为所有指数函数彼此之间的相似性都比二次函数或线性函数更大。

这是一个 YouTube 视频，说明了冒泡排序算法和快速排序算法之间的性能差异：https://www.youtube.com/watch?v=aXXWXz5rF64