大 O 符号备忘单及说明

披露：本帖包含附属链接；如果您通过本文提供的不同链接购买产品或服务，我可能会收到报酬。 信用 - DesignGuru.io

你好，开发人员，如果您正在准备编码面试，那么除了系统设计之外，您还需要准备数据结构和算法，并且您必须学习的一件事是Big(O) 符号。

在计算机科学和软件开发领域，效率是关键。

无论您是在优化代码、设计算法还是构建系统，了解算法和解决方案的性能特征都至关重要。

这就是大 O 符号发挥作用的地方。

大 O 符号提供了一种标准化的方法来描述算法的时间和空间复杂度，使开发人员能够定量地分析和比较不同的方法。

在几乎所有的编码面试中，当你展示你的解决方案时，面试官都会询问你算法的时间和空间复杂度。

他们还询问如何改善时间和空间，这就是时间与空间权衡的问题所在。

过去，我分享过一些系统设计面试问题，例如如何设计 WhatsApp 或 Facebook Messenger，或系统设计概念问题API 网关与负载均衡器、水平与垂直扩展、正向代理与反向代理之间的区别。

在本文中，我们将探讨每个开发人员都应该知道的八个基本大 O 符号，以便编写高效且可扩展的代码。

顺便说一句，如果你正在准备编码面试，并想深入学习数据结构、算法和系统设计，那么你也可以查看Design Guru、Exponent、Educative和Udemy等网站，它们有很多很棒的编码面试课程

如果你很着急，这里有一份来自DesignGuru.ioBig(O)的编码面试基本符号速查表，可以用来衡量你的算法的性能（从好到差）：

PS：请坚持读到最后。我有一个免费赠品给你。

每个开发人员都应该学习的 8 个基本 Big(O) 符号

让我们立即进入软件开发人员必备的 Big(O) 符号指南。

这对于您日常的编码以及在编码面试中取得好成绩非常有用。

1. O(1) --- 常数时间复杂度

时间复杂度为 O(1) 的算法具有恒定的运行时间，这意味着它们的执行时间不依赖于输入的大小。

对于任何算法来说，这都是最理想的性能。

例如，通过索引访问数组中的元素、执行基本算术运算或访问对象的属性都是常量时间O(1)操作。

无论你的数组包含 1 个元素还是10 亿个元素，你都可以同时使用索引访问它们。

它在图中的表现如下：

2. O(log n) --- 对数时间复杂度

具有时间复杂度的算法的O(log n)运行时间会随着输入大小的增加而呈对数增长。

这是继 O(1) 之后第二理想的性能，如果您无法针对 O(1) 进行优化，那么您应该至少尝试提高O(logN)算法的性能。

例如，二分查找算法就是具有对数时间复杂度的算法的一个很好的例子。在这种情况下，输入空间被反复分成两半。

对数复杂度如下

3. O（n）——线性时间复杂度

具有时间复杂度的算法的O(n)运行时间会随着输入的大小线性增长。这意味着随着数据的增加，算法的性能会以相同的比例下降。

大多数算法都属于这一类，例如线性搜索算法和各种链表操作，例如遍历链表或查找链表的长度。

例如，迭代数组或列表并对每个元素执行特定操作就是线性时间复杂度的一个例子。随着元素数量的增加，迭代时间也会按相同比例增加。

线性时间复杂度的图表如下：

4. O(n log n) --- 线性时间复杂度

具有时间复杂度的算法的O(n log n)运行时间与 n 的对数的 n 倍成比例增长。

由于额外的对数因子，这比线性时间算法更差。

例如，合并排序、快速排序和堆排序等高效排序算法具有 O(nlogn) 的时间复杂度。

它在图中的表现如下：

5. O（n²）——二次时间复杂度

具有时间复杂度的算法的O(n²)运行时间随着输入的大小呈二次增长。

这些都是速度较慢的算法，如果您提出任何具有二次时间复杂度的解决方案，您的面试官很可能会要求您改进它并将其降低到可接受的 O（n）或 O（logN）水平。

例如，嵌套循环中每次迭代执行线性操作，例如冒泡排序或选择排序。

图表中的情况如下：

6. O(2^n) --- 指数时间复杂度

这些算法又是最慢的，而且几乎总是不受欢迎的。时间复杂度为 O(2^n) 的算法，每增加一个输入元素，运行时间就会翻倍。

您可以使用缓存和记忆来提高此类算法的性能，以避免重新计算相同的数据。

例如，分支因子为 2 的递归算法，如斐波那契数列的朴素递归解。

图表中的情况如下：

7. O（n！）——阶乘时间复杂度

具有时间复杂度的计算机科学算法的O(n!)运行时间会随着输入的大小呈阶乘增长。这些算法也属于慢速算法，并不理想。

如果您的解决方案具有阶乘时间复杂度，那么请准备好改进它，因为面试官在大多数情况下不会接受它，除非它是一个非常复杂的问题并且这是唯一可能的解决方案。

生成集合的所有排列或组合的蛮力算法是阶乘时间复杂度算法的例子。

它在图中的表现如下：

8. O(n^c) --- 多项式时间复杂度

时间复杂度为 O(n^c) 的算法的运行时间随着输入的大小呈多项式增长，其中 c 是一个常数。

这是最慢的算法，也是开发人员应该知道的最后一个基本 Big(O) 符号。

例如，矩阵乘法算法就像Strassen算法一样具有多项式时间复杂度。

下面是一个包含所有 Big(O) 时间符号的图表，你可以看到情况如何从 O(1) 恶化到 O(2^n)

最佳编码面试资源

此外，这里还精心挑选了最佳编码面试书籍、在线课程和练习网站，您可以查看这些书籍、在线课程和练习网站，以更好地准备编码面试和 DSA、高级设计、低级设计等主题。

数字减影血管造影

如果你还生疏，可以先从以下几个最重要的面试问题开始：

Educative-99 - https://buff.ly/3LFG4zL（Python和 Java 版本）将教你 26 个关键的编码面试模式
Algomonster - http://shrsl.com/483tp（编码模式+问题）
盲人75：lnkd.in/g5wx7QSq
研磨 75：lnkd.in/gvZ7_pnp
使用您选择的语言练习 C++ STL 或 Java 集合或数据结构库——对于快速编码至关重要

低级设计（LLD）

1. 设计原则：阅读《Head First 设计模式》（阅读第二版）

OOP 概念应该非常清晰，例如 C++ 中的虚拟方法和抽象类与接口、重载与覆盖、方法隐藏等。

3. 问题：很棒的低级设计 - https://github.com/ashishps1/awesome-low-level-design ，由AlgoMaster 时事通讯的Ashish Pratap Singh撰写，我强烈推荐给程序员。

4. 使用 45 分钟计时器练习问题

5. 解决方案：低级设计播放列表 - lnkd.in/gkVZgK4b（感谢 Soumyajit Bhattacharyya）

高级设计（HLD）

1. 书籍：从Alex Xu 的第一卷和第二卷开始，或者在 Designgurus.io 上学习“Grokking the System Design Interview”课程

2. 视频：系统设计面试基本概念的良好渠道 - lnkd.in/gfEJppS3

4. 在 Pramp、tyrExponent上进行模拟面试（bit.ly/3cNF0vw和其他平台 - medium.com/javarevisited/3-best-mock-in...

5. 在Codeemia上以 Leetcode 风格练习系统设计问题- https://bit.ly/46AyaRJ

计算机科学基础

从 GateSmashers 视频中学习 - lnkd.in/gs6m5RQb

行为

1. 使用STAR 方法（情境、任务、行动、结果）

2. 保持每个部分简洁：每部分 4-5 句话，以便在面试时在规定时间内讲完

3. 准备详细和简短的答案

大 O 符号备忘单

另外，这里有一份来自 DesignGuru.io 的大 O 符号速查表，它是准备系统设计和编程面试的最佳网站之一。你也可以打印这份大 O 符号速查表，贴在办公桌上，以便快速参考。

信用 - DesignGuru.io

结论

以上就是这份Big O 符号速查表以及每个开发人员都应该学习的 8 个基本 Big(O) 符号的全部内容。理解 Big O 符号可以帮助开发人员客观地分析其算法的效率和可扩展性。

通过理解和记住这些基本的大 O 符号，您可以在选择或设计算法、优化性能和提高软件解决方案的可扩展性时做出明智的决策。

不断磨练算法分析和复杂性理论的技能无疑将增强您在各个软件开发领域编写高效、稳健代码的能力。

奖金

正如承诺的那样，这是给你的福利，一本免费的书。我刚刚找到了一本学习分布式系统设计的免费新书，你也可以在微软官网上阅读——https: //info.microsoft.com/rs/157-GQE-382/images/EN-CNTNT-eBook-DesigningDistributedSystems.pdf

谢谢

鏂囩珷鏉ユ簮锛�https://dev.to/somadevtoo/big-o-notations-cheatsheet-with-explanation-i2h