本章介绍了在技术面试中分析算法效率和可扩展性的最流行的指标——大 O 表示法。

有很多文章专门讨论这个主题。其中一些是纯粹的数学（学术），而另一些则试图用更友好的方法来解释它。纯数学方法很难消化，在面试中也不是很有用，所以我们会选择一种更友好的方法，面试官和开发人员会更熟悉。

即便如此，这也不是一项容易的任务，因为除了作为衡量算法效率和可扩展性的最流行指标外，Big O 表示法通常也是你从未有足够动力去学习的东西，尽管知道它是会出现在每一次采访中。从初级到高级战士，大 O 符号可能是每个人最大的阿喀琉斯之踵。然而，让我们努力把这个致命弱点变成我们采访的强项。

我们将快速回顾大 O 符号并突出显示最重要的事物。接下来，我们将跳入经过精心设计以涵盖广泛问题的示例，因此在本章结束时，您将能够确定和表达几乎任何给定代码片段的大 O。我们的议程包括以下内容：

• 比喻
• 大 O 复杂度时间
• 最好情况、最坏情况和预期情况
• 大 O 示例

那么，让我们开始我们的Big O之旅吧！

想象一个场景，您在互联网上找到了您最喜欢的电影之一。您可以订购或下载。既然你想尽快看到它，那么最好的方法是什么？如果您订购，则需要一天时间才能到达。如果你下载它，那么需要半天才能下载。因此，下载它会更快。这就是要走的路！

可是等等！就在您准备下载它时，您发现指环王大师合集的价格很高，因此您也考虑下载它。仅这一次，下载需要 2 天时间。但是，如果您下订单，那么它仍然只需要一天。所以，下单更快！

现在，我们可以得出结论，无论我们订购多少商品，运输时间都保持不变。我们称之为 O(1)。这是一个恒定的运行时间。

此外，我们得出结论，下载时间与文件大小成正比。我们称之为 O(n)。这是一个渐近运行时。

从日常观察中，我们还可以得出结论，在线订购的规模要好于在线下载。

这正是大 O 时间的含义：渐近运行时间测量或渐近函数。

作为渐近测量，我们谈论的是大 O 复杂度时间（这也可以是复杂度空间）。

下图显示，在某个时刻，O(n) 超过了 O(1)。因此，在 O(n) 超过 O(1) 之前，我们可以说 O(n) 的性能优于 O(1)：

图 7.1 – 渐近运行时间（大 O 时间）

除了 O(1) - 常数时间 - 和 O(n) - 线性时间运行时 - 我们还有许多其他运行时，例如 O(log n)、O(n log n) - 对数时间 - O(n2)—二次时间，O(2n)—指数时间，O(n!)—阶乘时间。这些是最常见的运行时，但还存在更多。

下图表示 Big O 复杂度图表：

图 7.2 – 大 O 复杂度图表

如您所见，并非所有 O 次都执行相同的操作。 O(n!)、O(2n) 和 O(n2) 被认为是 可怕，我们应该努力编写在这个领域之外执行的算法。 O(n log n) 比 O(n!) 好，但仍然 bad。 O(n) 被认为 fair，而 O(log n) 和 O(1) 被认为 good。

有时，我们需要多个变量来表达运行时性能。例如，在足球场上割草的时间可以表示为 O(wl)，其中 w 是足球场的宽度，l 是足球场的长度。或者，如果您必须修剪 p 足球场，则可以将其表示为 O(wlp)。

然而，这不仅仅是时间。我们也关心空间。例如，构建 n 元素的数组需要 O(n) 空间。构建 n x n 个元素的矩阵需要 O(n2)空间。

如果我们简化一些事情，那么我们可以根据最佳情况、最坏情况和预期情况来考虑我们算法的效率>。最好的情况是当我们的算法的输入满足一些允许其发挥最佳性能的特殊条件时。最坏的情况是在另一个极端，输入处于不利的形状，这使得我们的算法显示出其最差的性能。然而，这些惊人或可怕的情况通常不会发生。因此，我们介绍了预期的性能。

大多数时候，我们关心最坏和预期的情况，在大多数算法的情况下，它们通常是相同的。最好的情况是理想主义的表现，所以它仍然是理想主义的。主要是，对于几乎任何算法，我们都可以找到一个特殊的输入，它会导致 O(1) 的最佳情况性能。

有关 Big O 的更多详细信息，我强烈建议您阅读 Big O 备忘单 (https://www.bigocheatsheet.com/ ）。

现在，让我们处理一堆例子。

我们将尝试为不同的代码片段确定 Big O，就像您在面试中看到的那样，我们将学习几个需要学习的相关课程。换句话说，让我们采用通过示例学习的方法。

前六个示例将突出 Big O 的基本规则，如下所示：

• 丢弃常数
• 删除非主导项
• 不同的输入意味着不同的变量
• 不同的步骤相加或相乘

让我们从尝试示例开始。

Example 1 – O(1)

考虑以下三个代码片段并为每个片段计算 Big O：

// snippet 1
return 23;

由于此代码返回一个常数，因此大 O 为 O(1)。不管其余代码做什么，这行代码都将以恒定的速率执行：

// snippet 2 - 'cars' is an array 
int thirdCar = cars[3];

通过索引访问数组是用 O(1) 完成的。无论数组中有多少元素，从特定索引获取元素都是一个常量操作：

// snippet 3 - 'cars' is a 'java.util.Queue'
Car car = cars.peek();

Queue#peek() 方法检索但不删除此队列的头部（第一个元素）。头部后面有多少元素并不重要，通过 peek() 方法检索头部的时间是 O(1)。

因此，前面代码块中的所有三个片段都具有 O(1) 复杂度时间。类似地，从队列中插入和删除，从堆栈中压入和弹出，在链表中插入节点，以及检索存储在数组中的树的节点的左/右子节点也是 O(1) 时间的情况.

Example 2 – O(n), linear time algorithms

考虑以下代码片段并计算 Big O：

// snippet 1 - 'a' is an array
for (int i = 0; i < a.length; i++) {
    System.out.println(a[i]);
}

为了确定这段代码的大 O 值，我们必须回答以下问题：这样做了多少次for code> loop iterate? 答案是 a.length 次。我们不能确切地说这意味着多少时间，但我们可以说时间将随着给定数组（表示输入）的大小线性增长。因此，这段代码将有一个 O(a.length) 时间，称为线性时间。它表示为 O(n)。 

Example 3 – O(n), dropping the constants

考虑以下代码片段并计算 Big O：

// snippet 1 - 'a' is an array
for (int i = 0; i < a.length; i++) {
    System.out.println("Current element:");
    System.out.println(a[i]);
    System.out.println("Current element + 1:");
    System.out.println(a[i] + 1);
}

即使我们在循环中添加更多指令，我们仍将拥有与 Example 2 中相同的运行时间。运行时的输入大小仍然是线性的，a.length。正如在 Example 2 中，我们在一个循环中只有一行代码，而这里我们在一个循环中有四行代码，您可能期望 Big O 为 O(n + 4）或类似的东西。然而，这种推理并不精确或准确——它就是错误的！这里的大 O 仍然是 O(n)。

重要的提示

请记住，Big O 不依赖于代码行数。它取决于运行时的增长率，它不会被恒定时间操作修改。

为了强化这种情况，让我们考虑以下两个代码片段，它们计算给定数组 a 的最小值和最大值：

7.3 – 代码比较

现在，这两个代码片段中哪一个运行得更快？

第一个代码片段使用单个循环，但它有两个 if 语句，而第二个代码片段使用两个循环，但它有一个 if每个循环的 语句。

这样的想法打开了精神错乱的大门！计算语句可以在更深层次上继续。例如，我们可以继续在编译器级别计算语句（操作），或者我们可能想要考虑编译器优化。好吧，这不是 Big O 的意义所在！

重要的提示

Big O 并不是要计算代码语句。它的目标是表达输入大小的运行时增长并表达运行时如何扩展。简而言之，Big O 只是描述了运行时的增长率。

此外，不要误以为第一个片段有一个循环，大 O 是 O(n)，而在第二个片段的情况下，因为它有两个循环，大 O 是 O(2n) .只需从 2n 中删除 2，因为 2 是一个常数！

重要的提示

根据经验，当您表达 Big O 时，请在运行时删除常量。

因此，前面的两个片段都有一个 O(n) 的大 O 值。

示例 4 – 删除非主导项

考虑以下代码片段并计算 Big O（a 是一个数组）：

7.4 – 在 O(n) 中执行的代码片段

第一个 for 循环在 O(n) 中执行，而第二个 for 循环在 O(n2)。所以，我们可能认为这个问题的答案是 O(n) + O(n2) = O(n + n2< /跨度>）。但是这是错误的！增长率由 n2 给出，而 n 是非主导词。如果数组的大小增加，那么 n2 对增加率的影响远大于 n，因此 n 不相关。再考虑几个例子：

• O(2n + 2n) ->丢弃常数和非显性项-> O(2n)。
• O(n + log n) ->删除非主导词->上）。
• O(3*n2 + n + 2*n) -> drop constants and non-dominant terms -> O(n2).

  重要的提示

  根据经验，当您表达 Big O 时，请删除非主导项。

接下来，让我们关注两个常见的让候选人感到困惑的例子。

示例 5 – 不同的输入意味着不同的变量

考虑以下两个代码片段（a 和 b 是数组）。应该使用多少个变量来表示 Big O？

7.5 – 代码片段 1 和 2

在第一个片段中，我们有两个循环相同的数组 a 的 for 循环（两个循环的输入相同)，因此 Big O 可以表示为 O(n)，其中 n 指的是 a。在第二个代码片段中，我们还有两个 for 循环，但它们循环不同的数组（我们有两个输入，a 和b)。这一次，大 O 不是 O(n)！ n 指的是什么 - a 或 b？假设 n 指的是 a。如果我们增加 b 的大小，那么 O(n) 并不能反映运行时的增加率。因此，Big O 是这两个运行时的总和（a 的运行时加上 b 的运行时）。这意味着 Big O 必须同时引用这两个运行时。为此，我们可以使用两个变量来引用 a 和 b。因此，大 O 表示为 O(a + b)。这一次，如果我们增加 a 和/或 b 的大小，则 O(a + b) 捕获运行时速率增加。

重要的提示

根据经验，不同的输入意味着不同的变量。

接下来，让我们看看当我们将算法步骤相加和相乘时会发生什么。

Example 6 – different steps are summed or multiplied

考虑以下两个代码片段（a 和 b 是数组）。你如何表达每个片段的 Big O？

7.6 – 代码片段 a 和 b

从前面的示例中我们已经知道，在第一个片段的情况下，大 O 为 O(a + b)。我们总结了运行时，因为它们的工作不像第二个片段那样交织在一起。因此，在第二个片段中，我们无法总结运行时，因为对于 a[i] 的每种情况，代码都会循环 b< /code> 数组，所以大 O 是 O(a * b)。

在决定对运行时间求和或相乘之前，请三思而后行。这是面试中常见的错误。此外，很常见的是没有注意到输入不止一个（这里有两个），并且错误地使用单个变量来表达 Big O。那是错误的！始终注意存在多少输入。对于影响运行时增长率的每个输入，您应该有一个单独的变量（参见示例 5）。

重要的提示

根据经验，不同的步骤可以相加或相乘。运行时间应根据以下两个语句求和或相乘：

如果您将您的算法描述为 it foos 并且当它完成时，它会发出嗡嗡声，然后将运行时相加。

如果您将您的算法描述为每次失败，它都会发出嗡嗡声，然后乘以运行时间。

现在，让我们讨论 log n 运行时。

Example 7 – log n runtimes

编写一段伪代码，其大 O 为 O(log n)。

为了理解 O(log n) 运行时，让我们从二分搜索算法开始。二分搜索算法的详细信息和实现可在 第 14 章，排序和搜索。该算法描述了在数组 a 中查找元素 x 的步骤。考虑一个有 16 个元素的排序数组 a，如下所示：

图 7.7 – 16 个元素的有序数组

首先，我们将 x 与数组的中点 p 进行比较。如果它们相等，那么我们返回相应的数组索引作为最终结果。如果 x > p，然后我们在数组的右侧搜索。如果 x < p，然后我们在数组的左侧进行搜索。以下是查找数字 17 的二进制搜索算法的图形表示：

图 7.8 – 二分搜索算法

请注意，我们从 16 个元素开始，以 1 结束。在第一步之后，我们减少到 16/2 = 8 个元素。在第二步，我们减少到 8/2 = 4 个元素。在第三步，我们减少到 4/2 = 2 个元素。然后，在最后一步，我们找到了搜索到的数字，17。如果我们将这个算法翻译成伪代码，那么我们得到如下内容：

search 17 in {1, 4, 5, 7, 10, 16, 17, 18, 20, 
              23, 24, 25, 26, 30, 31, 33}
    compare 17 to 18 -> 17 < 18
    search 17 in {1, 4, 5, 7, 10, 16, 17, 18}
        compare 17 to 7 -> 17 > 7
        search 17 in {7, 10, 16, 17}
            compare 17 to 16 -> 17 > 16
            search 17 in {16, 17}
                compare 17 to 17
                return

现在，让我们为这个伪代码表达 Big O。我们可以观察到该算法由数组的连续半衰期组成，直到只剩下一个元素。因此，总运行时间取决于我们需要多少步才能在数组中找到某个数字。

在我们的示例中，我们有四个步骤（我们将数组减半 4 次），可以表示如下：

或者，如果我们压缩它，我们会得到：

更进一步，我们可以将其表示为 (n 是数组的大小，k 是数字达到解决方案的步骤）：

但是，2k = n 正是对数的含义 - 一个表示固定数（底数）必须提高到的幂的量产生一个给定的数字。所以，我们可以这样写：

在我们的例子中，2k = n 表示 24 = 16，这是 log216 = 4。

因此，二分搜索算法的大 O 为 O(log n)。但是，对数底在哪里？简短的回答是表示 Big O 不需要对数底，因为不同底的对数仅相差一个常数因子。

重要的提示

根据经验，当您必须为在每一步/迭代中将其输入减半的算法表示大 O 时，它很有可能是 O(log n) 的情况。

接下来，让我们谈谈对递归运行时的 Big O 进行评估。

示例 8 – 递归运行时

以下代码片段的大 O 是什么？

int fibonacci(int k) {
    if (k <= 1) {
        return k;
    }
    return fibonacci(k - 2) + fibonacci(k - 1);
}

在我们的第一印象中，我们可以将大 O 表示为 O(n2)。我们很可能会得到这个结果，因为我们被 return 中的 fibonacci() 方法的两次调用误导了。但是，让我们为 k 赋予价值并快速绘制运行时草图。例如，如果我们调用 fibonacci(7) 并将递归调用表示为一棵树，那么我们得到下图：

图 7.9 – 调用树

我们几乎立即注意到这棵树的深度等于 7，因此一般树的深度等于 k。此外，除了终端级别之外，每个节点都有两个子节点，因此几乎每个级别的调用次数都是上一级的两倍。这意味着我们可以将大 O 表示为 O(branches 深度)。在我们的例子中，这是 O(2k)，表示为 O(2n)。

在面试中，只说 O(2n) 应该是可以接受的答案。如果我们想要更准确，那么我们应该考虑终端级别，特别是最后一层（或调用堆栈的底部），有时可以包含单个调用。这意味着我们并不总是有两个分支。更准确的答案是 O(1.6n)。对于任何面试官来说，提到实际值小于 2 应该就足够了。

如果我们想用空间复杂度来表示大 O，那么我们得到 O(n)。不要被运行时复杂度为 O(2n) 的事实所迷惑。在任何时候，我们不能超过 k 个数字。如果我们查看前面的树，我们只能看到从 1 到 7 的数字。

Example 9 – in-order traversal of a binary tree

考虑给定的完美二叉搜索树。如果您需要快速剩余的二叉树，请考虑 第 13 章的 Nutshell 部分/em>, 树和图。下面这段代码的大 O 是什么？

void printInOrder(Node node) {
    if (node != null) {
       printInOrder(node.left);
       System.out.print(" " + node.element);
       printInOrder(node.right);
    }
}

完美二叉搜索树是一种二叉搜索树，其内部节点正好有两个子节点，并且所有叶节点都在同一级别或深度上。在下图中，我们有一个典型的完美二叉搜索树（同样，可视化运行时输入非常有用）：

图 7.10 – 高度平衡的二叉搜索树

我们从经验（更准确地说，从前面的例子中）知道，当我们遇到分支的递归问题时，我们可以有一个 O(branches depth) 的情况。在我们的例子中，我们有两个分支（每个节点有两个孩子），所以我们有 O(2 depth)。有一个指数时间看起来很奇怪，但是让我们看看节点数和深度之间的关系是什么。在上图中，我们有 15 个节点，深度为 4。如果我们有 7 个节点，那么深度就是 3，如果我们有 31 个节点，那么深度就是 5。现在，如果我们还没有从理论上知道完美二叉树的深度是对数的，那么也许我们可以观察到以下几点：

• 对于 15 个节点，我们的深度为 4；因此，我们有 24 = 16，相当于 log216 = 4。
• 对于 7 个节点，我们的深度为 3；因此，我们有 23 = 8，相当于 log28 = 3。
• 对于 31 个节点，我们的深度为 5；因此，我们有 25 = 32，相当于 log232 = 5。

根据前面的观察，我们可以得出结论，我们可以将大 O 表示为 O(2log n)，因为深度大致为 log n< /em>。所以，我们可以写如下：

图 7.11 – 大 O 表达式

因此，在这种情况下，大 O 为 O(n)。如果我们认识到这段代码实际上是二叉树的中序遍历，我们可以得出相同的结论，并且在这种遍历中（与前序和后序遍历完全相同），每个节点都被访问一个单次。此外，对于每个遍历的节点，都有恒定的工作量，因此 Big O 为 O(n)。

Example 10 – n may vary

以下代码片段的大 O 是什么？

void printFibonacci(int k) {
    for (int i = 0; i < k; i++) {
        System.out.println(i + ": " + fibonacci(i));
    }
}
int fibonacci(int k) {
    if (k <= 1) {
        return k;
    }
    return fibonacci(k - 2) + fibonacci(k - 1);
}

从例8中，我们已经知道fibonacci()方法的大O值为O(2n)。 printFibonacci() 调用 fibonacci() n 次，所以非常很想将 Big O 的总值表示为 O(n)*O(2n) = O(n2n)。然而，这是真的还是我们急于给出一个看似简单的答案？

好吧，这里的诀窍是 n 会有所不同。例如，让我们可视化运行时：

我们不能说 我们执行相同的代码 n 次，所以这是 O(2 n）。

Example 11 – memoization

以下 代码片段的大 O 是什么？

void printFibonacci(int k) {
    int[] cache = new int[k];
    for (int i = 0; i < k; i++) {
        System.out.println(i + ": " + fibonacci(i, cache));
    }
}
int fibonacci(int k, int[] cache) {
    if (k <= 1) {
        return k;
    } else if (cache[k] > 0) {
        return cache[k];
    }
    cache[k] = fibonacci(k - 2, cache) 
        + fibonacci(k - 1, cache);
    return cache[k];
}

此代码通过递归计算斐波那契数。但是，此代码使用了一种称为 Memoization 的技术。主要的想法是缓存返回值并使用它来减少递归调用。我们已经从 Example 8 知道 fibonacci() 方法的大 O 是 O(2n）。由于 Memoization 应该减少递归调用（它引入了优化），我们可以 猜测这段代码的 Big O 应该比O(2n)。然而，这只是一种直觉，所以让我们可视化 k = 7 的运行时：

Calling fibonacci(0):
Result of fibonacci(0) is 0
Calling fibonacci(1):
Result of fibonacci(1) is 1
Calling fibonacci(2):
	fibonacci(0)
	fibonacci(1)
	fibonacci(2) is computed and cached at cache[2]
Result of fibonacci(2) is 1
Calling fibonacci(3):
	fibonacci(1)
	fibonacci(2) is fetched from cache[2] as: 1
	fibonacci(3) is computed and cached at cache[3]
Result of fibonacci(3) is 2
Calling fibonacci(4):
	fibonacci(2) is fetched from cache[2] as: 1
	fibonacci(3) is fetched from cache[3] as: 2
	fibonacci(4) is computed and cached at cache[4]
Result of fibonacci(4) is 3
Calling fibonacci(5):
	fibonacci(3) is fetched from cache[3] as: 2
	fibonacci(4) is fetched from cache[4] as: 3
	fibonacci(5) is computed and cached at cache[5]
Result of fibonacci(5) is 5
Calling fibonacci(6):
	fibonacci(4) is fetched from cache[4] as: 3
	fibonacci(5) is fetched from cache[5] as: 5
	fibonacci(6) is computed and cached at cache[6]
Result of fibonacci(6) is 8

每个 fibonacci(k) 方法都是根据缓存的 fibonacci(k-1) 和 fibonacci(k-2) 方法。从缓存中获取计算值并将它们求和是一项恒定的时间工作。由于我们做了 这个工作k 次，这意味着大 O 可以表示为 O(n)。

除了 Memoization，我们还可以使用另一种方法，称为 Tabulation。 第 8 章中提供了更多详细信息a>，递归和动态规划。

示例 12 – 循环矩阵的一半

以下两段代码（a 是一个数组）的大 O 是什么？

7.12 – Big O 的代码片段

这些代码片段几乎相同，除了在第一个片段中，j 从 0 开始，而在第二个片段中，它从 i+1 开始。

我们可以轻松地为数组大小赋值，并可视化这两个代码片段的运行时间。例如，假设数组大小为 5。左边的矩阵是第一个代码片段的运行时间，而右边的矩阵对应于第二个代码片段的运行时间：

图 7.13 – 可视化运行时

对应第一个代码片段的矩阵显示 n*n 大小，而对应于第二个代码片段的矩阵大致显示 n*n/2 大小。所以，我们可以写如下：

• 片段 1 运行时为：。
• Snippet 2 运行时是： 因为我们消除了常量。

因此，两个代码片段都有 O(n2)。

或者，您可以这样想：

• 对于第一个片段，内部循环不起作用，它由外部循环运行 n 次，因此 n*n = n 2，结果为 O(n2)。
• 对于第二个片段，内部循环大致完成 n/2 次工作，并且它由外部循环运行 n 次，所以n*n/2 = n2/2 = n2 * 1/2，这导致（删除常量后）O(n2< /跨度>）。

Example 13 – identifying O(1) loops

以下代码片段的大 O 是什么（a 是一个数组）？

for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < a.length; j++) {
        for (int q = 0; q < 1_000_000; q++) {
            System.out.println(a[i] + a[j]);
        }
    }
}

如果我们忽略第三个循环（q 循环），那么我们已经知道大 O 是 O(n2)。那么，第三个循环如何影响总的 Big O 值呢？第三个循环从 0 迭代到 100 万，与 数组大小无关，因此该循环的大 O 为 O(1)，它是一个常数。由于第三个循环不依赖于输入大小的变化，我们可以这样写：

for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < a.length; j++) {
        // O(1)  
    }
}

现在，很明显这个例子的大 O 是 O(n2)。

Example 14 – looping half of the array

以下代码片段的大 O 是什么（a 是一个数组）？

for (int i = 0; i < a.length / 2; i++) {
    System.out.println(a[i]);
}

此处的混淆可能是由于此代码段仅循环了数组的一半。不要犯将大 O 表示为 O(n/2) 的常见错误。请记住，应该删除常量，因此 Big O 是 O(n)。仅迭代数组的一半不会影响 Big O 时间。

Example 15 – reducing Big O expressions

以下哪个可以表示为O(n)？

• O(n + p)
• O(n + log n)

答案是 O(n + log n) 可以简化为 O(n) 因为 log n 是一个非主导词，它可以被删除。另一方面，O(n + p) 不能简化为 O(n)，因为我们对 p 一无所知。直到我们确定p是什么以及n和p之间的关系是什么是，我们必须同时保留它们。

Example 16 – looping with O(log n)

以下代码片段（a 是一个数组）的大 O 是什么？

for (int i = 0; i < a.length; i++) {
    for (int j = a.length; j > 0; j /= 2) {
        System.out.println(a[i] + ", " + j);
    }
}

让我们只关注外循环。根据前面例子的经验，我们可以快速将大 O 表示为 O(n)。

内循环呢？我们可以注意到 j 从数组长度开始，并且在每次迭代中，它都减半。请记住 Example 7 中的重要说明： 当您必须为在每一步将输入减半的算法表示大 O 时，有O(log n) 情况下的机会很大。

重要的提示

每当您认为它很有可能是 O(log n) 的情况时，建议您使用作为除数幂的测试数字。如果输入除以 2（减半），则使用 2 的幂数（例如，23 = 8, 24 = 16、25 = 32，以此类推）。如果输入除以 3，则使用 3 的幂数（例如，32 = 9, 33 = 27，依此类推）。这样，很容易计算分区的数量。

因此，让我们为 a.length 赋予价值并可视化运行时。假设 a.length 为 16。这意味着 j 将采用 12、8、4、2 和 1价值观。我们将 j 除以 2 正好四次，所以我们有以下内容：

图 7.14 – 使用 O (log n) 的循环

因此，内部循环的大 O 为 O(log n)。为了计算总的 Big O，我们认为外部循环被执行 n 次，并且在该循环内，另一个循环被执行 log n 次。因此，Big O 的总结果为 O(n)* O (log n) = O(n log n)。

作为提示，许多排序算法（例如，合并排序和堆排序）都有 O(n log n) 运行时间。此外， 很多 O(n log n) 算法都是递归的。一般来说，属于分而治之（D&C）类别的算法 的算法是 O(n log n)。希望牢记这些技巧在面试中会非常方便。

Example 17 – string comparison

以下 代码片段的大 O 是什么？ （注意 a 是一个数组，一定要仔细阅读注释）：

String[] sortArrayOfString(String[] a) {
    for (int i = 0; i < a.length; i++) {
        // sort each string via O(n log n) algorithm           
    }
    // sort the array itself via O(n log n) algorithm               
    return a;
}

sortArrayOfString() 接收 String 数组并执行两个主要操作。它对该数组和数组本身的每个字符串进行排序。这两种排序都是通过运行时间表示为 O(n log n) 的算法完成的。

现在，让我们关注 for 循环，看看候选人通常给出的错误答案。我们已经知道对单个字符串进行排序会给我们 O(n log n)。对每个字符串执行此操作意味着 O(n) * (n log n) = O(n*n log n) = O(n2 log n)。接下来，我们对数组本身进行排序，也给出了 O(n log n)。将所有结果放在一起，总的 Big O 值为 O(n2 log n) + O(n log n) = O(n2 log n + n log n)，这是 O(n2 log n)，因为 n < em class="italic">log n 是一个非主导词。然而，这是正确的吗？最简洁的答案是不！但为什么不呢？！我们犯了两个主要错误：我们使用 n 来表示两件事（数组的大小和字符串的长度），我们假设比较String 与固定宽度整数一样需要恒定时间。

让我们详细说明第一个问题。因此，对单个字符串进行排序会给我们 O(n log n)，其中 n 表示该字符串的长度。我们对 a.length 字符串进行排序，因此 n 现在表示数组的大小。这就是混淆的来源，因为当我们说 for 循环是 O(n2 log n) 时，我们指的是哪个n？由于我们使用两个变量，我们需要以不同的方式表示。例如，我们可以考虑以下内容：

• s：最长String的长度。
• p：String数组的大小。

在这些术语中，对单个字符串进行排序是 O(s log s)，这样做 p 次会导致 O(p)*O(s log s) = O(p *s 日志 s)。

现在，让我们解决第二个问题。在我们的新术语中，对数组进行排序是 O(p log p)——我刚刚将 n 替换为 p。但是，String 的比较是否需要像固定宽度整数那样的恒定时间？答案是不！字符串排序改变了 O(p log p)，因为 String 比较本身具有可变成本。 String 的长度不同，因此比较时间也不同。因此，在我们的例子中，每个 String 比较需要 O(s)，并且由于我们有 O(p log p) 比较，结果是对字符串数组进行排序是 O( s) * O(p log p) = O(s*p log p)。

最后，我们必须将 O(p*s log s) 添加到 O(s*p log p) = O(s*p(log s + log p))。完毕！

Example 18 – factorial Big O

以下代码片段的大 O 是什么？

long factorial(int num) {
    if (num >= 1) {
        return num * factorial(num - 1);
    } else {
        return 1;
    }
}

很明显，这段代码是计算阶乘的递归实现。不要犯认为大 O 是 O(n!) 的常见错误。这不是真的！始终在没有先验假设的情况下仔细分析代码。

递归过程遍历序列n–1, n–2, ... 1次；因此，这是 O(n)。

Example 19 – using n notation with caution

以下两段代码的大 O 是什么？

7.15 – 代码片段

第一个片段（在左侧）持续工作 y 次。 x 输入不影响运行时增长率，因此大 O 可以表示为 O(y)。请注意，我们不说 O(n)，因为 n 也可能与 x 混淆。

第二个片段（在右侧）递归遍历 y-1, y-2, ..., 0 . 每个y输入被遍历一次，所以大O可以表示为O(y)。同样，x 输入不会影响运行时增长率。此外，我们避免说 O(n)，因为输入不止一个，O(n) 会造成混乱。

示例 20 – 总和和计数

以下代码片段（x 和 y 的大 O 是什么是积极的）？

int div(int x, int y) {
    int count = 0;
    int sum = y;
    while (sum <= x) {
       sum += y;
       count++;
    }
    return count;
}

让我们给 x 和 y 赋值并观察 count 变量，它计算迭代次数。考虑 x=10 和 y=2。对于这种情况，count 将为 5 (10/2 = 5)。按照同样的逻辑，我们 有 x=14, y=4 , count=3 (14/4 = 3.5), 或 x=22, y =3，或 count=7 (22/3 = 7.3)。我们可以注意到，在最坏的情况下，count 是 x/y ，所以大 O 可以表示为 O(x/y)。

Example 21 – the number of iteration counts in Big O

以下 代码片段尝试猜测数字的平方根。什么是大O？

int sqrt(int n) {
    for (int guess = 1; guess * guess <= n; guess++) {
        if (guess * guess == n) {
            return guess;
        }
    }
    return -1;
}

假设数字 (n) 是一个完美的平方根，例如 144，我们已经知道 sqrt(144) = 12。由于 guess 变量从 1 开始并在步骤 1 中停止在 guess*guess <= n，计算 guess 将取值 1, 2, 3, ... , 12。当 guess 为 12 时，我们有 12*12 = 144，而循环停止。所以，我们有 12 次迭代，正好是 sqrt(144)。

对于非完美平方根，我们遵循相同的逻辑。假设 n 是 15。这一次，guess 将采用 1、2 和 3 的值。当 guess=4 时，我们有 4*4 > 15，循环停止。返回的 值为-1。因此，我们进行了 3 次迭代。

总之，我们有 sqrt(n) 迭代，所以大 O 可以表示为 O(sqrt(n))。

Example 22 – digits

以下 代码片段总结了整数的位数。什么是大O？

int sumDigits(int n) {
    int result = 0;
    while (n > 0) {
        result += n % 10;
        n /= 10;
    }
    return result;
}

在每次迭代中，n 除以 10。这样，代码就会隔离数字右侧的一个数字（例如，56643/10 = 5664.3）。为了遍历所有数字，while 循环需要与数字数量相等的迭代次数（例如，对于 56,643，它需要 5 次迭代来隔离 3、4、6、 6 和 5）。

但是，一个 5 位数字最多可以达到 105 = 100,000，这意味着 99,999 次迭代。一般来说，这意味着一个具有 d 个数字的数字 (n) 最多可以有 10 个 d。所以，我们可以这样说：

图 7.16 – 数字关系

Example 23 – sorting

以下 代码片段的大 O 是什么？

boolean matching(int[] x, int[] y) {
    mergesort(y);
    for (int i : x) {
        if (binarySearch(y, i) >= 0) {
            return true;
        }
    }
    return false;
}

在 Example 16 中，我们说过很多排序算法（包括 Merge Sort）的运行时间为 O(n log n)。这意味着 mergesort(y) 的运行时间为 O(y log y)。

在Example 7中，我们说二分搜索算法的运行时间为 O(log n)。这意味着 binarySearch(y, i) 的运行时间为 O(log y)。在最坏的情况下，for 循环将迭代整个 x 数组，因此将执行二分查找算法x.length 次。 for 循环的运行时间为 O(x log y)。

因此，总的 Big O 值可以 表示为 O(y log y) + O(x log y) = O(y log y + x log y)。

完毕！这是这里展示的最后一个例子。接下来，我们尝试提炼出几个关键提示，可以帮助你在面试中判断和表达大O。

在采访中，时间和压力是影响注意力的严重因素。拥有识别模板、识别特定案例、猜出正确答案等的能力会给您带来重大优势。正如我们在 第 5 章中所述，如何应对编码挑战， 在图 5.2 中，构建示例（或用例）是应对编码挑战的第二步。即使面试官给出了代码，构建一个示例对于确定大 O 仍然非常有用。

正如您可能注意到的那样，在我们介绍的几乎所有重要示例中，我们更愿意为一个或几个具体案例可视化运行时。这样，您可以真正了解代码的细节，识别输入，确定代码的静态（常量）和动态（可变）部分，并大致了解代码的工作原理。

以下是可以在面试中帮助您的关键提示的非详尽列表：

• 如果算法做常数工作，那么大O就是O(1)：这种例子使用输入来执行常数工作（例如，取三个整数，x、y、w，并做一些计算，如x-y 和 y*w)。在某些情况下，为了造成混淆，它还会添加重复语句（例如，计算是在 for(int i=0; i<10; i++) 中完成的）。因此，从一开始就确定算法的输入是否影响其运行时间非常重要。
• 如果算法循环整个数组或列表，那么总的Big O值可能涉及O(n)：通常，代码片段包含一个或多个循环的重复语句整个输入，通常是一个数组或列表（例如，for(int i=0; i ，其中 a 是一个数组)。通常，这些结构的运行时间为 O(n)。在某些情况下，为了造成混淆，重复结构会添加一个条件来验证 break 语句。请记住，Big O 是关于最坏情况的情况，因此您应该评估运行时，记住验证 break 语句的条件可能永远不会发生并且 Big O 仍然是 O (n)。
• 如果在每次迭代中，算法将输入数据减半，那么 O(log n) 可能涉及到总的 Big O 值：正如您在 例 7，二分搜索算法是一个 O(log n) 的著名案例。通常，您可以通过尝试可视化运行时来识别类似情况。
• 具有分支的递归问题是一个很好的信号，表明 O(branches depth)总大 O 值的一部分：遇到 O(2depth) 的最常见情况是在操作二叉树的代码片段中。还要注意如何确定 depth。正如您在 Example 9 中看到的，depth 会影响最终结果。在这种情况下，O(2log n) 减少到 O(n)。
• 使用记忆法或制表法的递归算法非常适合将 O(n) 作为其总 Big O 值：通常，递归算法会暴露指数运行时间（例如，O(2< span class="superscript">n))，但 Memoization 和 Tabulation 等优化可能会将运行时间缩短到上）。
• 排序算法通常会在总 Big O 值中引入 O(n log n)：请记住，很多排序算法（例如，堆排序、合并排序等） on) 的运行时间为 O(n log n)。

我希望这些提示对您有所帮助，因为我们已经介绍了一些经过验证的示例。

在本章中，我们介绍了面试中最主要的主题之一，Big O。有时，您必须为给定的代码确定 Big O，而其他时候，您必须为自己的代码确定它。换句话说，在面试中绕过大O的可能性很小。不管你训练得多么努力，Big O 始终是一个很难的话题，即使是最优秀的开发人员也会陷入困境。幸运的是，这里介绍的案例是面试中最受欢迎的案例，它们代表了许多衍生问题的完美模板。

在下一章中，我们将讨论面试中其他受欢迎的话题：递归和动态编程。