理解大 O 表示法：时间和空间复杂性初学者指南

想象一下我们有不同的方式来编写相同的代码。我们如何判断哪一个是最好的？这就是 Big O 表示法的用武之地。它可以帮助我们衡量代码需要多少时间和空间，从而更容易比较它们。

什么是大 O 表示法？

Big O，也称为“顺序”，是描述算法在最坏情况下运行所需时间的一种方式。它让我们了解算法根据输入大小所需的最大时间。我们将其写为 O(f(n))，其中 f(n) 表示算法解决输入大小为 n 的问题需要多少步。

让我们尝试通过示例来理解“编写一个接受字符串输入并返回反向副本的函数”

好吧，我正在与您分享一个 Stack Overflow 解决方案，以及上图，如您所见。它展示了解决同一问题的 10 种不同方法，每种方法都有独特的方法。

现在的问题是：我们如何知道哪一个是最好的？

我们的目标是理解时间和空间复杂性。为此，让我们探索一个包含两个不同代码片段的具体示例，以便我们可以清楚地了解这些概念的重要性。

这是一个名为 addUpTo 的函数。该函数使用 for 循环，运行直到达到 n 的长度并返回总和。

现在，让我们看另一个实现相同功能的示例：

哪一个更好？

现在，在这种情况下“更好”到底意味着什么？

• 更快吗？

• 它使用的内存较少吗？

• 可读性更好吗？

通常，人们在考虑可读性之前会关注前两个因素——速度和内存使用情况。在这种情况下，我们将重点关注前两个。为了测量两个代码示例的性能，我们将使用 JavaScript 的内置计时函数来分析和比较它们的执行时间。

在上面的代码中，我添加了 t1 和 t2，它们利用了 JavaScript 中内置的 Performance.now() 函数。这个函数帮助我们测量代码执行所花费的时间，使我们能够准确地比较两种方法的性能。

确实，执行时间根据不同因素而有所不同，你在我的电脑上也可以看到——时间不一致。 Performance.now() 函数没有给我们一个固定的时间，但它提供了一个有用的比较估计。

现在，让我们看第二个例子：

现在，观察第一个和第二个代码示例之间执行时间的差异。第二个明显比第一个快。

但是仅仅依赖时间测量有什么问题呢？

• 不同机器记录的时间不同。

• 即使是同一台机器，每次运行也会记录不同的时间。

• 对于非常快的算法，速度测量可能不够精确，无法进行准确的比较。

这些因素使得基于时间的性能评估不可靠，尤其是对于快速算法。

好吧，如果没时间那怎么办？

这就是 Big O 将帮助我们衡量时间复杂度和空间复杂度的地方。所以大O表示法是一种形式化模糊计数的方法。它使我们能够正式讨论算法的运行时间如何随着输入的增长而增长。

如果随着 n 的增加，计算机必须执行的简单操作的数量最终小于常数乘以 f(n)，则我们称算法为 O(f(n))。

• f(n) 可以是线性的 (f(n) = n)

• f(n) 可以是二次方 (f(n) = n2)

• f(n) 可以是常数 (f(n) = 1)

• f(n) 可能完全不同！

这是一个例子：

在这种情况下，我们只有 3 个操作，无论输入的大小，它总是保持 3 个操作。这就是为什么我们可以说这个函数的时间复杂度是常数，或者O(1).

现在这是第一个示例：

在这种情况下，随着输入 n 的增长，操作数量也会成比例增加。因此，时间复杂度取决于输入的大小，使其O(n).

现在，让我们看另一个例子：

在此示例中，我们有两个嵌套的 for 循环，都依赖于 n（输入）。这意味着随着输入n的增长，操作数量显着增加。因此，这段代码的时间复杂度为 O(n²)，也称为二次时间复杂度。

现在，让我们简化大O表示法。在确定算法的时间复杂度时，需要记住一些有用的经验规则。这些指南源自 Big O 表示法的正式定义，使分析算法变得更加容易。

常数并不重要

• O(2n) = O(n)

• O(500) = O(1)

• O(13n²) = O(n²)

• O(n 10) = O(n)

• O(1000n 500) = O(n)

• O(n² 5n 8) = O(n²)

大 O 速记

1. 算术运算是常数

2. 变量赋值是常量

3. 访问数组（按索引）或对象（按键）中的元素是常量

4. 在循环中，复杂度是循环的长度乘以循环内发生的任何事情的复杂度

这是大 O 图表：

到目前为止，从示例中，我们已经了解了 O(n)（线性时间复杂度）、O(1)（恒定时间复杂度）和 O(n²)（二次时间复杂度）。这些涵盖了操作随输入大小而增长的基本模式。

稍后我们将讨论 O(log n) 和 O(n log n)——对数和线性时间复杂度。

空间复杂度

到目前为止，我们一直关注时间复杂度：随着输入大小的增加，我们如何分析算法的运行时间？

我们还可以使用大 O 表示法来分析空间复杂度：我们需要分配多少额外内存才能运行算法中的代码？

输入怎么样？

有时您会听到术语“辅助空间复杂度”，指的是算法所需的空间，不包括输入占用的空间。除非另有说明，当我们谈论空间复杂度时，从技术上讲，我们将谈论辅助空间复杂度。

JS 中的空间复杂度

• 大多数基元（布尔值、数字、未定义、null）都是常量空间

• 字符串需要 O(n) 空间（其中 n 是字符串长度） 引用类型通常是 O(n)，其中 n 是长度（对于数组）或键的数量（对于对象）

记住，我们谈论的是空间复杂度，而不是时间复杂度。在这段代码中，我们可以看到只有两个变量。无论输入增长多大，这两个变量将始终存在于代码中。由于随着输入的增加，我们没有添加任何新变量，因此我们可以说空间复杂度为 O(1)，这意味着它是恒定的空间复杂度。

让我们用另一个例子来理解：

在此代码中，函数在将输入数组中的每个元素加倍后返回 newArr。由于newArr的大小与输入arr的大小成正比，因此newArr使用的空间随着输入大小的增加而增长。与前面的示例不同，其中空间是恒定的，这里的空间复杂度取决于输入数组的大小。因此，空间复杂度为O(n)，意味着它是线性的。

我希望这能让空间复杂度更加清晰——就像时间复杂度一样，我们使用 Big O 表示法来测量它。到目前为止，您已经了解了不同的时间复杂度，按复杂度递增的顺序：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(n3) 等等。然而，我们还没有探索对数时间复杂度。

接下来，我们将深入研究对数时间复杂度并看看它是如何工作的。

对数

我们遇到了一些最常见的复杂性：O(1)、O(n)、O(n2)。有时大 O 表达式涉及更复杂的数学表达式。对数出现得比你想象的更频繁！

日志又是什么？

log2 (8) = 3 → 2³ = 8

log2（值）= 指数 → 2^指数 = 值

我们将省略 2，这意味着：

log === log2

数字的对数大致衡量在该数字小于或等于 1 之前您可以将该数字除以 2 的次数。这使得对数时间复杂度非常高效。正如您在图表中看到的，O(1)（恒定时间）非常接近 O(log n)，这太棒了！还值得注意的是，O(n log n) 在效率方面比 O(n²) 好得多，使其成为许多算法的首选复杂度。

• 某些搜索算法具有对数时间复杂度。

• 高效的排序算法涉及对数。

• 递归有时涉及对数空间复杂度。

太棒了！我们已经涵盖了空间和时间复杂度的大部分关键点。请记住，掌握这些概念需要练习，因此如果不能立即完全清楚，请不要感到不知所措。慢慢来，多次查看材料，并根据需要重新查看示例。通常需要重复几次才能真正理解这些想法，所以对自己要有耐心！

最后，让我们再回顾一下：

• 为了分析算法的性能，我们使用大 O 表示法

• 大 O 表示法可以让我们对算法的时间或空间复杂度有一个高层次的理解

• 大 O 表示法不关心精度，只关心总体趋势（线性？二次？常数？）

再说一遍，大 O 表示法无处不在，所以要多加练习！

---

我们CreoWis相信公开分享知识可以帮助开发者社区成长。让我们充满激情地协作、构思和打造，为世界提供令人惊叹的产品体验。

让我们联系：

• X/Twitter

• 领英

• 网站

本文由 CreoWis 的一位充满热情的开发人员 Syket Bhattachergee 撰写。您可以通过 X/Twitter、LinkedIn、 联系他，并在 GitHub 上关注他的工作。

以上是理解大 O 表示法：时间和空间复杂性初学者指南的详细内容。更多信息请关注PHP中文网其他相关文章！