大 O 表示法：它是什么以及为什么它很重要？

这很有趣！对于早期职业开发者来说，与 Big O 沟通是第一个令人心碎的转变之一。

让我们看看为什么。

但首先，进站。你还记得小学时那些绝对可笑的应用题吗？

莎莉去杂货店买了 37 个西瓜。她有20美元。每个西瓜售价 0.70 美元。莎莉回家后有多少钱？

您是否想知道，“莎莉到底要怎么回家？带着 37 个西瓜？！6 美元还不够叫一辆有足够空间容纳西瓜的 Uber……莎莉在做什么？！”

愚蠢的莎莉。

有人说，这是只见树木不见森林。我说这只是一种非常懒惰的构建练习问题的方法。

大 O 表示法的目的是能够与其他人谈论我们的工艺质量，从字面上进行交流。这里特别关注的是随着输入大小的增加，在最坏情况下对解决方案进行比较。

我们希望能够抽象地讨论潜在的解决方案（与算法相同）。这是一个关键点：在抽象中。我们根本不关心我们拥有的数据。当我们研究这些想法时，我们假设一个理论上巨大但有限的数据集。

当我们思考我们所拥有的数据时，这就是具体的推理。当我们想到大 O 表示法时，我们是在进行抽象推理。很容易回到具体的推理。这是我们度过一生大部分时间的地方。它很简单，通常很明显，而且很舒服。

我现在应该过马路吗？有车吗？不？好吧，交叉。

抽象推理时不要这样做！

快速定义

你介意我在这里帮你一个忙吗？还有一些数学术语也可能会造成妨碍。下面是一些常见 Big O 术语的视觉效果，按从最佳情况到最坏的顺序排列。我们需要这些，以便我们可以进行思考和学习，而不是陷入术语之中。

O(1) - “恒定时间”

无论输入有多大，系统总是在相同的时间内返回结果。

O(log n) - “记录时间”

随着解决方案（或算法）迭代输入，每次迭代都会变得更快！

O(n) - “线性时间”

当算法迭代时，每次迭代所花费的时间与前一次迭代相同。

O(n log n) -这里没有花哨的术语

表明这些想法可以结合起来（哎呀）。当我们迭代时，每次迭代都会变慢，但变慢的速度相当慢。

O(n^2) - “n 平方”

对于每次迭代，迭代速度都会很快变慢。

O(n!) - “n 阶乘”

对于每次迭代，迭代速度都会变得非常慢。

目标是尽量远离“n 阶乘”，并尽量不要比 Constant 差很多。

了解了所有这些之后，现在让我们尝试弥合差距。

弥合具体思维和抽象思维之间的差距

理解大 O 表示法

大 O 表示法用于描述算法（解决方案）的性能或复杂性。它提供了对算法（解决方案）如何随着输入大小的增长而执行的高级理解。

例如，复杂度为 O(n) 的算法的运行时间将随着输入的大小线性增加。

具体思维与抽象思维

当开发人员将特定数据的推理误认为算法本身的推理时，就会出现挑战。诸如“但这些数据是真实的”之类的短语可能表明了这种混乱。

虽然推理真实数据可以帮助您入门，但将解决方案与当前输入分开至关重要。

为什么会产生误解？

早期职业开发人员可能会因为缺乏解决更大规模问题的经验或过于专注于当前问题的细节而犯这个错误。必须将具体细节与抽象复杂性分开，以创建可扩展的解决方案。

实际后果

当输入增加 100 倍或 100,000 倍时，算法会发生什么？一个极其复杂的解决方案可能会随着数据集的增大而崩溃。

对于小数据集看似良好的算法可能会在较大数据集上显着失败，从而导致性能问题和其他挑战。

学习抽象思考

培养抽象思考问题的能力需要实践和指导。一些策略包括：

• 创建抽象模型：以通用的方式表示问题。

• 与数据分开分析算法：评估算法的行为方式，而不考虑特定的数据点。

• 构建扩展场景：想象算法如何在不同大小的输入下执行。

一般来说，抽象思维，特别是大 O 表示法，是算法设计中的基本技能——换句话说，就是提出问题的解决方案。

通过学习将问题复杂性与算法复杂性分开，开发人员可以避免常见的陷阱，提高单独工作时解决问题的能力，并显着提高与其他同样投入时间学习如何以这种方式进行沟通的人一起工作的能力。

复杂的问题通常不需要复杂的解决方案。 （莎莉一开始可能不需要 37 个西瓜……她要用 37 个西瓜做什么？！）