算法分析

在上一节中，我们已经完成了我们的算法。但有一件事我们还没有做，那就是对我们的算法进行分析。在当前情况下，一个合理的问题是，为什么我们真的需要对算法进行分析？虽然我们已经编写了实现方法，但我们并不确定我们编写的代码将利用多少资源。我们所说的资源是指运行应用程序所使用的时间和存储资源。我们编写的算法可以处理任何长度的输入。

为了了解我们的算法在输入变大时的表现，以及利用了多少资源，我们通常通过将输入长度与步骤数（时间复杂度）或存储量（空间复杂度）相关联来衡量算法的效率。为了找到最有效的算法来解决问题，对算法进行分析是非常重要的。

我们可以在两个不同的阶段进行算法分析。一个是在执行之前，一个是在执行之后。实施前的分析也称为理论分析，我们假设其他因素（如处理能力和空间）保持不变。实施后的分析被称为算法的经验分析，它可以因平台或语言而异。在经验分析中，我们可以从系统中获得有关时间和空间利用率的可靠统计数据。

对于我们放置图书和从购买的物品中查找图书的算法，我们也可以进行类似的分析。目前，我们更关注的是时间复杂性，而不是空间复杂性。我们将在接下来的章节中探讨空间复杂性。

计算复杂度

我们在算法分析中测量两种类型的复杂性：

  • 时间复杂性：时间复杂度以算法中关键操作的数量来衡量。换句话说，时间复杂度量化了算法从开始到结束所需的时间。

  • 空间复杂度：空间复杂度定义了算法在其生命周期中所需的空间（内存）。它取决于数据结构和平台的选择。

现在，让我们关注一下我们实现的算法，并了解一下我们为算法所做的操作。在我们的 placeAllBooks 函数中，我们正在搜索我们订购的每一本书。因此，如果我们有 10 本书，我们就要搜索 10 次。如果数量是 1000 本，我们就要搜索 1000 次。因此，我们可以简单地说，如果有 n 本图书，我们就要搜索 n 次。在算法分析中，输入数大多用 n 表示。

对于已订购图书中的每个项目，我们都要使用 findABook 函数进行搜索。在该函数中，我们再次使用从 placeAllBooks 函数中获得的名称搜索每一本已收到的图书。现在，如果我们足够幸运，我们可以在已收到图书列表的开头找到该书的名称。在这种情况下，我们就不必搜索其余的项目了。但如果我们非常不走运，我们要搜索的书在列表的末尾呢？我们就必须逐本搜索，最后才能找到。如果收到的图书数也是 n，那么我们就必须进行 n 次比较。

如果我们假设其他操作都是固定的，那么唯一的变量就是输入的大小。然后，我们就可以定义一个边界或数学公式来定义这种情况，以计算其运行时的性能。我们称之为渐进分析。渐进分析是以输入为边界的，这意味着如果没有输入，其他因素都是不变的。我们使用渐近分析找出算法的最佳情况、最差情况和平均情况：

  • 最佳情况：最佳情况表示执行程序所需的最短时间。对于我们的示例算法，最佳情况可能是，对于每本书，我们只搜索第一项。因此，我们最终搜索的时间非常短。我们使用 Ω 符号（西格玛符号）来表示最佳情况。

  • 平均情况：表示执行程序所需的平均时间。对于我们的算法来说，平均情况是大部分时间在列表中间找到图书，或者一半时间在列表开头，剩下一半时间在列表结尾。

  • 最坏情况：它表示程序的最长运行时间。最坏情况的例子是一直在列表末尾找到图书。我们使用 O(big oh) 符号来描述最坏情况。在我们的算法中，每查找一本书都需要 O(n) 的运行时间。从现在起，我们将使用这个符号来表示我们算法的复杂性。