大O符号和纸杯蛋糕
这篇文章是根据我的会议演讲“有趣、友好的计算机科学”改编的一系列文章的第一篇。
我厨艺很差。其实，可能也不完全是这样，我只是真的不喜欢做饭，所以从来不在这方面花心思。但如果你不像我这样，而且喜欢待在厨房里，你或许就能凭借食材比例而不是食谱做出美味的菜肴。
烹饪时使用比例，是指不死记硬背食谱，而是记住各种食材的比例。所需食材的量会根据你想做的食物份量而相应变化。例如，纸杯蛋糕的比例是 4:3:2:1，即 4 个鸡蛋、3 杯面粉、2 杯糖和 1 杯黄油。
那么，大O符号和纸杯蛋糕有什么关系呢？大O符号衡量的是函数或算法的相对复杂度。它衡量的是复杂度与函数输入规模的比例关系。
通常情况下，复杂度指的是运行时间，但也可以用来衡量内存消耗、堆栈深度和其他资源。我们将重点关注运行时间，因为在编程面试中，面试官通常会问到这一点。由于我们讨论的是相对复杂度，因此实际的输入规模并不重要，因为我们想要衡量的是代码的比例复杂度。这一点将在我们的示例中得到更清晰的说明。
从本质上讲，大O符号是对复杂度的一种数学表示。它是一种函数式表示法，可以将所有“O”表示在图表上，这对于那些更擅长视觉或图形处理的人来说很有帮助。
如果您不喜欢图片，这篇文章也会提供代码示例。本文的示例是用 JavaScript 编写的，您可以在这里找到；如果您更熟悉Ruby或Python ，我也提供了这两种语言的示例。
O(1)
你可能遇到的第一个“O”是 O(1)（读作 O of 1）。O(1) 表示运行时间恒定。随着输入规模的增加，代码的执行时间保持不变。
举个例子，如果你要做纸杯蛋糕，就需要将黄油和糖一起搅拌3分钟。所以，无论你做一份还是两份纸杯蛋糕，都需要3分钟来混合黄油和糖。
combineButterAndSugar(batches) {
const steps = [];
const butter = {
ingredient: this.recipeRatios.butter,
amount: batches * this.recipeRatios.butter.number
};
const sugar = {
ingredient: this.recipeRatios.sugar,
amount: batches * this.recipeRatios.sugar.number
};
steps.push(this.beatWithMixer([butter, sugar], 3));
steps.push("Combined butter and sugar: O(1)");
return steps.join("<br/>");
}
在）
接下来是 O(n)。函数的运行时间与输入规模成正比。换句话说，随着输入规模的增加，执行时间线性增加。
单个 for 循环或 while 循环是判断一个函数是否为 O(n) 的一个好方法。例如，在制作纸杯蛋糕时，我们需要一次加入一个鸡蛋，然后用电动搅拌器搅拌 1 分钟。如果每批纸杯蛋糕需要 4 个鸡蛋，那么步骤如下：1) 加入一个鸡蛋，搅拌 1 分钟；2) 加入一个鸡蛋，搅拌 1 分钟；3) 加入一个鸡蛋，搅拌 1 分钟；4) 加入一个鸡蛋，搅拌 1 分钟。您可能会注意到，实际运行时间是 4n，但在大 O 表示法中，系数并不重要。我们衡量的是相对复杂度，而用 n 来表示复杂度已经足够精确，无需用系数来增加精确度。
addEggs(batches) {
const steps = [];
const oneEgg = { ingredient: this.recipeRatios.eggs, amount: 1 };
const butterMixture = { ingredient: "butter mixture" };
const amount = batches * this.recipeRatios.eggs.number;
for (let egg = 0; egg < amount; egg++) {
steps.push(this.beatWithMixer([oneEgg, butterMixture], 1));
}
steps.push("Added eggs: O(n)");
return steps.join("<br/>");
}
O(n^2)
下一个“O”的性能稍有下降。O(n^2) 表示运行时间与输入规模的平方成正比。
复杂度与输入规模的平方成正比，这看似不常见，但实际上非常普遍。任何时候遇到嵌套循环，你很可能都在处理 O(n^2) 或其类似的复杂度。随着嵌套循环深度的增加，指数也会增加。因此，嵌套两层的循环是 O(n^2)，三层的是 O(n^3)，四层的是 O(n^4)，以此类推。
combineFlourMixtureAndMilkAndButterMixture(batches) {
const steps = [];
const butterMixture = { ingredient: "butter mixture" };
const flourMixture = { ingredient: "flour mixture" };
const milk = {
ingredient: this.recipeRatios.milk,
amount:
(batches * this.recipeRatios.milk.number) / (batches * batches)
};
steps.push(this.beatWithMixer([butterMixture, flourMixture], 1));
for (let batch = 0; batch < batches; batch++) {
for (let portion = 0; portion < batches; portion++) {
steps.push(this.beatWithMixer([butterMixture, milk], 1));
steps.push(this.beatWithMixer([butterMixture, flourMixture], 1));
}
}
steps.push("Slowly combined milk, flour mixture, and butter mixture: O(n^2)");
return steps.join("<br/>");
}
O(2^n)
当代码执行时间随输入规模呈指数增长时，时间复杂度就达到了 O(2^n)。这意味着输入规模的微小增加会导致运行时间的显著增加。
递归计算斐波那契数列就是一个 O(2^n) 算法的例子。如果我们为斐波那契举办生日派对，想在纸杯蛋糕上用糖霜写上斐波那契数列，那么随着蛋糕数量的增加，算法的运行时间将呈指数级增长。（我们很快会讲解递归，所以如果你之前没接触过递归，也不用担心。）
fibonacciFrosting(batches) {
const numberToFrost = this.calculateFibonacciNumber(batches);
return `Iced the fibonacci number ${numberToFrost} to all of the cupcakes: O(2^n)`;
}
calculateFibonacciNumber(number) {
if (number <= 1) {
console.log("Fibonacci base case!");
return number;
}
return this.calculateFibonacciNumber(number - 1) + this.calculateFibonacciNumber(number - 2);
}
O(log n)
最后，我们来看对数运行时间。我把 O(log n) 看作是 O(2^n) 的倒数。指数增长会导致运行时间随着输入规模的增长而不断增大，而对数增长则会导致运行时间随着输入规模的增长而不断减小，直到输入规模足够大时，运行时间趋于一个常数。
我没有现成的代码示例，因为我用纸杯蛋糕做比喻有点牵强了😬，但对数时间复杂度在分治算法（例如二分查找）中很常见。如果我们想用对数时间复杂度的算法来分发纸杯蛋糕，我们可以把蛋糕切成两半，分别交给离我们最近的两个人，然后让他们再把各自的蛋糕切成两半，分别交给离他们最近的两个人，以此类推，直到每个人都分到一个蛋糕为止。
大O符号的使用
大O符号可能会让人望而生畏，因为如果你从未有机会学习过它，就很难根据上下文推断出它的含义。在我10年的编程生涯中，除了大学计算机科学课程和面试之外，我从未用过大O符号。因此，在你面试新工作之前，不妨温习一下，以防你的面试官更看重计算机科学基础知识，而不是其他（在我看来）更有价值的技能。
大O表示法也很有用，它能帮助你与同事们用统一的语言讨论代码的相对性能。但如果你记不住不同的“O”及其含义，也别觉得不好意思。统一的语言固然好，但你也可以指出嵌套循环对性能的负面影响，而无需记住它对应的是哪个“O”🤗
文章来源：https://dev.to/mercedes/big-o-notation-and-cupcakes-2l6