“Big O”符号的简单英文解释是什么？
我更喜欢尽可能少的正式定义和简单的数学。
快速说明，我的回答几乎肯定会将 Big Oh notation （这是一个上限）与 Big Theta 表示法“Θ”（这是一个两侧的界限）混淆。但根据我的经验，这实际上是非学术环境中的典型讨论。对造成的任何混乱表示歉意。
BigOh 复杂度可以用这个图来可视化：
https://i.stack.imgur.com/WcBRI.png
我可以为 Big Oh 符号给出的最简单的定义是：
Big Oh 表示法是算法复杂性的相对表示。
这句话中有一些重要且故意选择的词：
相对：您只能将苹果与苹果进行比较。您无法将进行算术乘法的算法与对整数列表进行排序的算法进行比较。但是比较两种算法来进行算术运算（一个乘法，一个加法）会告诉你一些有意义的事情；表示：BigOh（以最简单的形式）将算法之间的比较简化为单个变量。该变量是根据观察或假设选择的。例如，排序算法通常基于比较操作（比较两个节点以确定它们的相对顺序）进行比较。这假设比较是昂贵的。但是，如果比较便宜但交换很昂贵怎么办？它改变了比较；和复杂性：如果我需要一秒钟来对 10,000 个元素进行排序，那么我需要多长时间才能对 100 万个元素进行排序？在这种情况下，复杂性是对其他事物的相对衡量。
阅读完其余部分后，请返回并重新阅读以上内容。
我能想到的 BigOh 最好的例子就是做算术。取两个数字（123456 和 789012）。我们在学校学到的基本算术运算是：
添加;减法；乘法;和分裂。
这些中的每一个都是一个操作或一个问题。解决这些问题的方法称为算法。
加法是最简单的。您将数字排成一行（向右）并将数字添加到一列中，在结果中写入该加法的最后一个数字。该数字的“十”部分被转移到下一列。
让我们假设这些数字的相加是该算法中最昂贵的操作。理所当然地，要将这两个数字相加，我们必须将 6 个数字相加（并且可能带有第 7 个数字）。如果我们将两个 100 位数字相加，我们必须进行 100 次加法。如果我们将两个 10,000 位数字相加，我们必须进行 10,000 次加法。
看到图案了吗？复杂度（即操作数）与较大数字中的位数 n 成正比。我们称之为 O(n) 或线性复杂度。
减法是类似的（除了你可能需要借而不是进位）。
乘法不同。您将数字排成一行，取底部数字中的第一个数字，然后将其与顶部数字中的每个数字依次相乘，依此类推。因此，要将我们的两个 6 位数字相乘，我们必须进行 36 次乘法。我们可能还需要添加多达 10 或 11 列才能获得最终结果。
如果我们有两个 100 位数字，我们需要进行 10,000 次乘法和 200 次加法。对于两个一百万位的数字，我们需要进行一万亿（1012）次乘法和两百万次加法。
由于算法以 n 平方进行缩放，因此这是 O(n2) 或二次复杂度。现在是介绍另一个重要概念的好时机：
我们只关心复杂性中最重要的部分。
精明的人可能已经意识到我们可以将操作数表示为：n2 + 2n。但正如您从我们的示例中看到的，每个数字都有两个百万位数，第二项 (2n) 变得微不足道（占该阶段总操作的 0.0002%）。
可以注意到，我们在这里假设了最坏的情况。在乘以 6 位数字时，如果其中一个有 4 位，另一个有 6 位，那么我们只有 24 次乘法。尽管如此，我们还是计算了那个“n”的最坏情况，即当两者都是 6 位数字时。因此，Big Oh 表示法是关于算法的最坏情况。
电话簿
我能想到的下一个最好的例子是电话簿，通常称为白页或类似名称，但它因国家而异。但我说的是按姓氏，然后是首字母或名字，可能是地址，然后是电话号码的人。
现在，如果你让计算机在包含 1,000,000 个姓名的电话簿中查找“John Smith”的电话号码，你会怎么做？忽略你可以猜到 S 开始多远的事实（假设你不能），你会怎么做？
一个典型的实现可能是打开中间，取第 500,000 个并将其与“Smith”进行比较。如果它恰好是“史密斯，约翰”，我们真的很幸运。更有可能的是，“John Smith”将出现在该名称之前或之后。如果是在我们之后将电话簿的后半部分分成两半并重复。如果在此之前，我们将电话簿的前半部分分成两半并重复。等等。
这称为二进制搜索，无论您是否意识到，每天都会在编程中使用它。
因此，如果您想在包含一百万个名字的电话簿中找到一个名字，您实际上最多可以通过这样做 20 次来找到任何名字。在比较搜索算法时，我们决定这个比较是我们的“n”。
对于 3 个姓名的电话簿，最多需要 2 次比较。 7 个最多需要 3 个。15 个需要 4 个。…… 1,000,000 个需要 20 个。
这真是太好了，不是吗？
在 BigOh 术语中，这是 O(log n) 或对数复杂度。现在有问题的对数可能是 ln（以 e 为底）、log10、log2 或其他一些底。没关系，它仍然是 O(log n)，就像 O(2n2) 和 O(100n2) 仍然都是 O(n2)。
在这一点上值得解释一下，BigOh 可用于通过算法确定三种情况：
最佳情况：在电话簿搜索中，最好的情况是我们在一次比较中找到姓名。这是 O(1) 或恒定复杂度；预期情况：如上所述，这是 O(log n);最坏情况：这也是 O(log n)。
通常我们不关心最好的情况。我们对预期和最坏的情况感兴趣。有时其中一个或另一个会更重要。
回到电话簿。
如果您有电话号码并想查找姓名怎么办？警方有一个反向电话簿，但公众拒绝进行此类查找。还是他们？从技术上讲，您可以反向查找普通电话簿中的号码。如何？
您从名字开始并比较数字。如果这是一场比赛，很好，如果不是，你继续下一场。你必须这样做，因为电话簿是无序的（无论如何都是通过电话号码）。
因此，要查找给定电话号码的名称（反向查找）：
最佳情况：O(1)；预期情况：O(n)（对于 500,000）；最坏情况：O(n)（对于 1,000,000）。
旅行推销员
这是计算机科学中一个非常著名的问题，值得一提。在这个问题中，你有 N 个城镇。这些城镇中的每一个都通过一定距离的道路与一个或多个其他城镇相连。旅行推销员问题是找到访问每个城镇的最短路径。
听起来很简单？再想想。
如果您有 3 个城镇 A、B 和 C，所有对之间都有道路，那么您可以去：
A → B → CA → C → BB → C → AB → A → CC → A → BC → B → A
嗯，实际上比这要少，因为其中一些是等价的（例如，A → B → C 和 C → B → A 是等价的，因为它们使用相同的道路，只是相反）。
实际上，有3种可能。
把它带到 4 个城镇，你就有（iirc）12 种可能性。 5 等于 60。6 变为 360。
这是称为阶乘的数学运算的函数。基本上：
5！ = 5 × 4 × 3 × 2 × 1 = 120 6！ = 6 × 5 × 4 × 3 × 2 × 1 = 720 7！ = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040 … 25！ = 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000 … 50！ = 50 × 49 × … × 2 × 1 = 3.04140932 × 1064
所以旅行推销员问题的 BigOh 是 O(n!) 或阶乘或组合复杂度。
当你到达 200 个城镇时，宇宙中已经没有足够的时间来解决传统计算机的问题了。
需要考虑的事情。
多项式时间
我想快速提及的另一点是，任何具有 O(na) 复杂度的算法都被称为具有多项式复杂度或可在多项式时间内求解。
O(n)、O(n2) 等都是多项式时间。有些问题不能在多项式时间内解决。正因为如此，世界上使用了某些东西。 Public Key Cryptography 就是一个很好的例子。在计算上很难找到两个非常大的素数。如果不是，我们就无法使用我们使用的公钥系统。
无论如何，这就是我对 BigOh（修订版）的（希望是简单的英语）解释。
它显示了算法如何根据输入大小进行缩放。
O(n2)：称为二次复杂度
项：1 次操作
10 项：100 次操作
100 项：10,000 次操作
请注意，项目的数量增加了 10 倍，但时间增加了 102 倍。基本上，n=10，所以 O(n2) 给我们的比例因子 n2 是 102。
O(n)：称为线性复杂度
项：1 次操作
10 项：10 次操作
100 项：100 次操作
这次项目的数量增加了 10 倍，时间也是如此。 n=10，因此 O(n) 的比例因子为 10。
O(1)：称为常数复杂度
项：1 次操作
10 项：1 次操作
100 项：1 次操作
项目的数量仍然增加了 10 倍，但 O(1) 的比例因子始终为 1。
O(log n)：称为对数复杂度
项：1 次操作
10 项：2 次操作
100 项：3 次操作
1000 项：4 次操作
10,000 项：5 次操作
计算次数仅增加输入值的对数。所以在这种情况下，假设每次计算需要 1 秒，输入 n 的日志就是所需的时间，因此是 log n。
这就是它的要点。他们减少了数学，所以它可能不完全是 n2 或他们所说的任何东西，但这将是缩放的主要因素。
Big-O 表示法（也称为“渐近增长”表示法）是当您忽略原点附近的常数因子和东西时，函数“看起来像”的样子。我们用它来谈论事物如何扩展。
基本
对于“足够”大的输入......
f(x) ∈ O(upperbound) 表示 f“增长不快于”上界
f(x) ∈ Ɵ(justlikethis) 表示 f “长得一模一样” justlikethis
f(x) ∈ Ω(lowerbound) 表示 f“增长不慢于”下限
big-O 表示法不关心常数因子：函数 9x² 被称为“完全像”10x²。 big-O asymptotic 表示法也不关心 non-asymptotic 东西（“靠近原点的东西”或“当问题规模很小时会发生什么”）：函数 { 2} 据说“长得完全像”10x² - x + 2。
为什么要忽略等式的较小部分？因为当你考虑越来越大的尺度时，它们与方程的大部分相比变得完全相形见绌；他们的贡献变得渺小和无关紧要。 （参见示例部分。）
换句话说，当你走向无穷大时，这一切都与比率有关。 如果您将实际花费的时间除以 O(...)，您将得到一个限制大输入限制的常数因子。 直观地说，这是有道理的：如果您可以相乘，函数会“相互缩放”一个得到另一个。那就是当我们说...
actualAlgorithmTime(N) ∈ O(bound(N))
e.g. "time to mergesort N elements
is O(N log(N))"
...这意味着对于“足够大”的问题大小 N（如果我们忽略原点附近的东西），存在一些常数（例如 2.5，完全组成），使得：
actualAlgorithmTime(N) e.g. "mergesort_duration(N) "
────────────────────── < constant ───────────────────── < 2.5
bound(N) N log(N)
常数有多种选择；通常“最佳”选择被称为算法的“常数因子”......但我们经常忽略它，就像我们忽略非最大项一样（请参阅常数因子部分了解它们通常不重要的原因）。您还可以将上述等式视为一个界限，即“在最坏的情况下，它所花费的时间永远不会比大约 N*log(N) 差，在 2.5 的因子内（我们没有的常数因子”不太在乎）”。
一般来说，O(...) 是最有用的，因为我们经常关心最坏情况的行为。如果 f(x) 表示诸如处理器或内存使用情况之类的“坏”情况，则“f(x) ∈ O(upperbound)”表示“upperbound 是处理器/内存使用的最坏情况”。
应用
作为一个纯粹的数学结构，大 O 表示法不限于谈论处理时间和内存。您可以使用它来讨论缩放有意义的任何事物的渐近线，例如：
聚会中 N 人之间可能握手的次数（Ɵ(N²)，特别是 N(N-1)/2，但重要的是它“像”N² 一样缩放）
将一些病毒式营销视为时间函数的概率预期人数
网站延迟如何随着 CPU、GPU 或计算机集群中处理单元的数量而扩展
CPU 芯片上的热量输出如何随晶体管数量、电压等的变化而变化。
算法需要运行多少时间，作为输入大小的函数
作为输入大小的函数，算法需要运行多少空间
例子
对于上面的握手示例，房间中的每个人都与其他人握手。在该示例中，#handshakes ∈ Ɵ(N²)。为什么？
稍微备份一下：握手的次数正好是 n-choose-2 或 N*(N-1)/2 （N 个人中的每个人都与 N-1 其他人握手，但是这个双重计数握手所以除以 2）：
https://i.stack.imgur.com/L4HUw.png
然而，对于非常多的人，线性项 N 相形见绌，有效地为比率贡献了 0（在图表中：对角线上的空框占总框的比例随着参与者数量的增加而变小） .因此缩放行为是 order N²，或者握手的次数“像 N² 一样增长”。
#handshakes(N)
────────────── ≈ 1/2
N²
就好像图表对角线上的空框（N*(N-1)/2 个复选标记）甚至不存在（N2 个复选标记渐近）。
（从“普通英语”暂时离题：）如果您想向自己证明这一点，您可以对比率执行一些简单的代数以将其拆分为多个项（lim 表示“考虑到的限制”，请忽略如果你还没有看到它，它只是“N 真的很大”的符号）：
N²/2 - N/2 (N²)/2 N/2 1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞ N² N→∞ N² N² N→∞ 1
┕━━━┙
this is 0 in the limit of N→∞:
graph it, or plug in a really large number for N
tl;dr：对于大值，握手的次数“看起来像”x² 如此之多，如果我们写下比率#handshakes/x²，我们不需要完全 x² 握手的事实甚至不会出现在十进制中任意大的一段时间。
例如对于 x=100 万，比率 #handshakes/x²：0.499999...
建立直觉
这让我们可以做出如下陈述......
“对于足够大的输入大小 = N，无论常数因子是多少，如果我将输入大小加倍......
...我将 O(N)（“线性时间”）算法所花费的时间加倍。”
N → (2N) = 2(N)
...我将 O(N²)（“二次时间”）算法所花费的时间平方（四倍）。”（例如，100 倍大的问题需要 100²=10000 倍的时间......可能不可持续）
N² → (2N)² = 4(N²)
...我将 O(N³)（“立方时间”）算法花费的时间加倍（八倍）。”（例如，100 倍大的问题需要 100³=1000000 倍的时间……非常不可持续）
cN³ → c(2N)³ = 8(cN³)
...我在 O(log(N))（“对数时间”）算法所花费的时间上加上一个固定的量。”（便宜！）
c log(N) → c log(2N) = (c log(2))+(c log(N)) = (固定数量)+(c log(N))
...我不会更改 O(1)（“恒定时间”）算法所花费的时间。”（最便宜的！）
c*1 → c*1
...我“（基本上）加倍”了 O(N log(N)) 算法所花费的时间。”（相当常见）
c 2N log(2N) / c N log(N) （这里我们将 f(2n)/f(n) 相除，但我们可以像上面那样按摩表达式并分解出 cNlogN）→ 2 log(2N)/ log(N) → 2 (log(2) + log(N))/log(N) → 2*(1+(log2N)-1) （对于大 N 基本上是 2；最终小于 2.000001）（或者，比如说对于您的数据，log(N) 将始终低于 17，因此它是 O(17 N)，它是线性的；虽然这既不严谨也不合理）
...我荒谬地增加了 O(2N)（“指数时间”）算法所花费的时间。”（你可以通过将问题增加一个单位来增加一倍（或三倍等）时间）
2N → 22N = (4N)............换一种说法...... 2N → 2N+1 = 2N21 = 2 2N
[对于数学倾向，您可以将鼠标悬停在剧透上以获取较小的旁注]
（归功于 https://stackoverflow.com/a/487292/711085 ）
（从技术上讲，常数因素在一些更深奥的例子中可能很重要，但我已经在上面说了一些事情（例如在 log(N) 中），所以它没有）
这些是程序员和应用计算机科学家用作参考点的基本增长顺序。他们总是看到这些。 （因此，虽然您在技术上可以认为“将输入加倍会使 O(√N) 算法慢 1.414 倍”，但最好将其视为“这比对数差，但比线性好”。）
常数因子
通常，我们并不关心具体的常数因子是什么，因为它们不会影响函数的增长方式。例如，两种算法可能都需要 O(N) 时间才能完成，但一种可能比另一种慢两倍。我们通常不会太在意，除非因素非常大，因为优化是一件棘手的事情（When is optimisation premature?）；同样，仅仅选择具有更好大 O 算法的行为通常会提高性能几个数量级。
一些渐近优越的算法（例如，非比较 O(N log(log(N))) 排序）可能具有如此大的常数因子（例如 100000*N log(log(N))），或者像 O(N log(log(N))) 和隐藏 + 100*N 的开销相对较大，以至于它们很少即使在“大数据”上也值得使用。
为什么 O(N) 有时是你能做的最好的，即为什么我们需要数据结构
O(N) 如果您需要读取所有数据，算法在某种意义上是“最佳”算法。 读取一堆数据的行为是一个O(N)操作。将其加载到内存中通常是 O(N)（如果您有硬件支持，则速度更快，或者如果您已经读取数据，则根本没有时间）。但是，如果您触摸甚至查看每条数据（甚至每条其他数据），您的算法将花费 O(N) 时间来执行此查看。无论您的实际算法需要多长时间，都至少需要 O(N)，因为它花费了这段时间查看所有数据。
写作本身也是如此。所有打印出 N 东西的算法都需要 N 时间，因为输出至少有那么长（例如打印出所有排列（重新排列的方法）一组 N 扑克牌是阶乘：O(N!)（这就是为什么在这些情况下，好的程序将确保迭代使用 O(1) 内存并且不会打印或存储每个中间步骤））。
这激发了数据结构的使用：一个数据结构只需要读取一次数据（通常是 O(N) 次），外加一些任意数量的预处理（例如 O(N) 或 O(N log(N)) 或 {4 }) 我们尽量保持小。此后，修改数据结构（插入/删除/等）并对数据进行查询只需很少的时间，例如 O(1) 或 O(log(N))。然后您继续进行大量查询！一般来说，你愿意提前做的工作越多，你以后要做的工作就越少。
例如，假设您拥有数百万条路段的经纬度坐标，并且想要查找所有街道交叉口。
朴素的方法：如果你有一个街道交叉口的坐标，并且想检查附近的街道，你必须每次都经过数百万个路段，并检查每个路段是否相邻。
如果你只需要做一次，那么 O(N) 的朴素方法只做一次是没有问题的，但是如果你想做很多次（在这种情况下，N次，一次为每个段），我们必须做 O(N²) 的工作，或者 1000000²=1000000000000 次操作。不好（现代计算机每秒可以执行大约十亿次操作）。
如果我们使用一种称为哈希表（一种即时查找表，也称为哈希图或字典）的简单结构，我们会通过在 O(N) 时间内对所有内容进行预处理来支付少量成本。此后，通过它的键查找某个东西平均只需要恒定的时间（在这种情况下，我们的键是纬度和经度坐标，四舍五入成一个网格；我们搜索只有 9 个相邻的网格空间，这是一个持续的）。
我们的任务从不可行的 O(N²) 变为可管理的 O(N)，我们所要做的就是支付少量成本来制作哈希表。
类比：这个特殊案例中的类比是一个拼图游戏：我们创建了一个利用数据的某些属性的数据结构。如果我们的路段就像拼图一样，我们通过匹配颜色和图案对它们进行分组。然后我们利用这一点来避免以后做额外的工作（比较相同颜色的拼图，而不是与其他每个拼图）。
故事的寓意：数据结构让我们加快操作速度。更重要的是，高级数据结构可以让您以非常聪明的方式组合、延迟甚至忽略操作。不同的问题会有不同的类比，但它们都涉及以利用我们关心的某种结构的方式组织数据，或者我们为了记账而人为地强加给它的结构。我们确实提前工作（基本上是计划和组织），现在重复的任务要容易得多！
实际示例：在编码时可视化增长顺序
从本质上讲，渐近符号与编程完全不同。渐近符号是一种数学框架，用于思考事物如何扩展并可以用于许多不同的领域。也就是说......这就是您将渐近符号应用于编码的方式。
基础知识：每当我们与大小为 A 的集合中的每个元素（例如数组、集合、映射的所有键等）进行交互，或者执行循环的 A 次迭代时，这就是大小为 A 的乘法因子. 为什么我说“乘法因子”？--因为循环和函数（几乎按照定义）具有乘法运行时间：迭代次数，循环中完成的工作时间（或函数：调用的次数函数，函数中完成的时间）。 （如果我们不做任何花哨的事情，比如跳过循环或提前退出循环，或者根据参数更改函数中的控制流，这很常见。）这里有一些可视化技术的例子，并附有伪代码。
（这里，x 代表恒定时间的工作单元、处理器指令、解释器操作码等）
for(i=0; i<A; i++) // A * ...
some O(1) operation // 1
--> A*1 --> O(A) time
visualization:
|<------ A ------->|
1 2 3 4 5 x x ... x
other languages, multiplying orders of growth:
javascript, O(A) time and space
someListOfSizeA.map((x,i) => [x,i])
python, O(rows*cols) time and space
[[r*c for c in range(cols)] for r in range(rows)]
示例 2：
for every x in listOfSizeA: // A * (...
some O(1) operation // 1
some O(B) operation // B
for every y in listOfSizeC: // C * (...
some O(1) operation // 1))
--> O(A*(1 + B + C))
O(A*(B+C)) (1 is dwarfed)
visualization:
|<------ A ------->|
1 x x x x x x ... x
2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v
x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v
示例 3：
function nSquaredFunction(n) {
total = 0
for i in 1..n: // N *
for j in 1..n: // N *
total += i*k // 1
return total
}
// O(n^2)
function nCubedFunction(a) {
for i in 1..n: // A *
print(nSquaredFunction(a)) // A^2
}
// O(a^3)
如果我们做一些稍微复杂的事情，你可能仍然能够直观地想象发生了什么：
for x in range(A):
for y in range(1..x):
simpleOperation(x*y)
x x x x x x x x x x |
x x x x x x x x x |
x x x x x x x x |
x x x x x x x |
x x x x x x |
x x x x x |
x x x x |
x x x |
x x |
x___________________|
在这里，您可以绘制的最小可识别轮廓很重要；三角形是二维形状（0.5 A^2），就像正方形是二维形状（A^2）；这里的常数因子 2 保留在两者之间的渐近比中，但是，我们像所有因子一样忽略它......（我不在这里讨论这种技术的一些不幸的细微差别；它可能会误导你。）
当然这并不意味着循环和函数不好；相反，它们是现代编程语言的基石，我们喜欢它们。但是，我们可以看到，我们将循环、函数和条件与我们的数据（控制流等）编织在一起的方式模仿了我们程序的时间和空间使用！如果时间和空间使用成为问题，那就是当我们求助于聪明并找到一个我们没有考虑过的简单算法或数据结构时，以某种方式降低增长顺序。尽管如此，这些可视化技术（尽管它们并不总是有效）可以让您天真地猜测最坏情况下的运行时间。
这是我们可以在视觉上识别的另一件事：
<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x
我们可以重新排列它，看看它是 O(N)：
<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x
或者，也许您对数据进行 log(N) 次传递，总时间为 O(N*log(N))：
<----------------------------- N ----------------------------->
^ x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
| x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
| x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
v x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x
无关但值得再次提及：如果我们执行哈希（例如字典/哈希表查找），那是 O(1) 的一个因素。这相当快。
[myDictionary.has(x) for x in listOfSizeA]
\----- O(1) ------/
--> A*1 --> O(A)
如果我们做一些非常复杂的事情，例如使用递归函数或分治算法， 您可以使用 Master Theorem（通常有效），或者在荒谬的情况下使用 Akra-Bazzi 定理（几乎总是有效） 你在维基百科上查找你的算法的运行时间。
但是，程序员不会这样想，因为最终，算法直觉会成为第二天性。您将开始编写一些低效的代码并立即思考“我在做一些非常低效的事情吗？”。如果答案是“是”并且您预见到它实际上很重要，那么您可以退后一步，想出各种技巧来让事情运行得更快（答案几乎总是“使用哈希表”，很少“使用树”，很少有更复杂的东西）。
摊销和平均案例复杂度
还有“摊销”和/或“平均情况”的概念（请注意，这些是不同的）。
平均情况：这只不过是对函数的期望值使用大 O 表示法，而不是函数本身。在通常情况下，您认为所有输入的可能性相同，平均情况只是运行时间的平均值。例如，对于快速排序，即使对于某些非常糟糕的输入，最坏情况是 O(N^2)，但平均情况是通常的 O(N log(N))（真正糟糕的输入数量非常少，以至于我们没有注意到它们在平均情况下）。
摊销的最坏情况：某些数据结构的最坏情况复杂度可能很大，但保证如果您执行许多此类操作，您所做的平均工作量将优于最坏情况-案子。例如，您可能有一个通常需要常数 O(1) 时间的数据结构。但是，有时它会“打嗝”并花费 O(N) 时间进行一次随机操作，因为它可能需要做一些簿记或垃圾收集或其他事情......但它向您保证，如果它打嗝，它不会打嗝再次进行 N 次以上的操作。最坏情况的成本仍然是每次操作 O(N)，但多次运行的摊销成本是每次操作 O(N)/N = O(1)。由于大型操作很少见，因此可以将大量的临时工作视为与其余工作融为一体的恒定因素。我们说这项工作在足够多的调用中“摊销”了，它会逐渐消失。
摊销分析的类比：你开车。有时，您需要花 10 分钟去加油站，然后花 1 分钟给油箱加满油。如果你每次开着车去任何地方都这样做（花 10 分钟开车到加油站，花几秒钟加满几分之一加仑），那将是非常低效的。但是，如果你每隔几天给油箱加满油，那么开车到加油站所花的 11 分钟就会在足够多的行程中“摊销”，你可以忽略它，假装你所有的行程可能长了 5%。
平均情况和摊销的最坏情况之间的比较：
平均情况：我们对输入做出一些假设；即，如果我们的输入具有不同的概率，那么我们的输出/运行时将具有不同的概率（我们取其平均值）。通常，我们假设我们的输入都是等可能的（统一概率），但如果现实世界的输入不符合我们的“平均输入”假设，则平均输出/运行时计算可能毫无意义。但是，如果您预期均匀随机输入，那么考虑一下这一点很有用！
摊销的最坏情况：如果您使用摊销的最坏情况数据结构，则性能保证在摊销的最坏情况内......最终（即使输入是由一个知道一切并试图把你搞砸了）。通常，我们使用它来分析性能可能非常“不稳定”的算法，这些算法可能会出现意想不到的大问题，但随着时间的推移，它们的性能与其他算法一样好。 （但是，除非您的数据结构对它愿意拖延的许多未完成的工作有上限，否则邪恶的攻击者可能会迫使您一次性完成最大数量的拖延工作。
但是，如果您是reasonably worried攻击者，那么除了摊销和平均情况之外，还有许多其他算法攻击向量需要担心。）
平均情况和摊销都是非常有用的工具，用于思考和设计时要考虑规模。
（如果对此子主题感兴趣，请参阅 Difference between average case and amortized analysis。）
多维大O
大多数时候，人们没有意识到有不止一个变量在起作用。例如，在字符串搜索算法中，您的算法可能需要时间 O([length of text] + [length of query])，即它在两个变量（如 O(N+M)）中是线性的。其他更简单的算法可能是 O([length of text]*[length of query]) 或 O(N*M)。忽略多个变量是我在算法分析中看到的最常见的疏忽之一，并且会在设计算法时妨碍您。
整个故事
请记住，big-O 并不是故事的全部。您可以通过使用缓存来显着加速某些算法，使它们无需缓存，通过使用 RAM 而不是磁盘来避免瓶颈，使用并行化或提前完成工作——这些技术通常独立于增长顺序“big-O”表示法，尽管您经常会在并行算法的 big-O 表示法中看到内核数量。
还要记住，由于程序的隐藏约束，您可能并不真正关心渐近行为。您可能正在使用有限数量的值，例如：
如果您要对 5 个元素进行排序，则不想使用快速的 O(N log(N)) 快速排序；您想使用插入排序，它恰好在小输入上表现良好。这些情况经常出现在分治算法中，在这种算法中，您将问题分解为越来越小的子问题，例如递归排序、快速傅立叶变换或矩阵乘法。
如果某些值由于某些隐藏的事实而被有效限制（例如，平均人名被软限制在大约 40 个字母，而人类年龄被软限制在 150 左右）。您还可以对输入施加限制，以有效地使术语保持不变。
在实践中，即使在具有相同或相似渐近性能的算法中，它们的相对优点实际上也可能受到其他因素的驱动，例如：其他性能因素（快速排序和归并排序都是O(N log(N))，但快速排序利用了 CPU 缓存） ;非性能考虑，例如易于实施；图书馆是否可用，以及图书馆的声誉和维护情况如何。
程序在 500MHz 计算机上的运行速度也会比 2GHz 计算机慢。我们并没有真正将其视为资源界限的一部分，因为我们认为缩放是根据机器资源（例如每个时钟周期），而不是每实际秒。但是，也有类似的事情会“秘密地”影响性能，例如您是否在仿真下运行，或者编译器是否优化了代码。这些可能会使一些基本操作花费更长的时间（甚至相对于彼此），甚至会渐近地加速或减慢一些操作（甚至相对于彼此）。不同实现和/或环境之间的影响可能很小或很大。你会切换语言或机器来勉强完成那一点额外的工作吗？这取决于其他一百个原因（必要性、技能、同事、程序员的生产力、您时间的货币价值、熟悉度、变通方法、为什么不组装或 GPU 等...），这可能比性能更重要。
上述问题，例如选择使用哪种编程语言的影响，几乎从未被视为常量因素的一部分（也不应该如此）；但是应该注意它们，因为有时（尽管很少）它们可能会影响事物。例如，在 cpython 中，本机优先级队列实现是渐近非最优的（O(log(N)) 而不是 O(1) 供您选择插入或 find-min）；你使用其他实现吗？可能不会，因为 C 实现可能更快，并且其他地方可能还有其他类似的问题。有权衡；有时它们很重要，有时它们不重要。
（编辑：“简单的英语”解释到此结束。）
数学附录
为了完整起见，big-O 表示法的精确定义如下： f(x) ∈ O(g(x)) 表示“f 由 const*g 渐近上界”：忽略 x 的某个有限值以下的所有内容，存在这样的常数那个|f(x)| ≤ const * |g(x)|。 （其他符号如下：就像 O 表示≤，Ω 表示≥。有小写变体：o 表示 <，ω 表示 >。）f(x) ∈ Ɵ(g(x)) 表示 {1 } 和 f(x) ∈ Ω(g(x))（以 g 为上限和下限）：存在一些常数，使得 f 始终位于 const1*g(x) 和 const2*g(x) 之间的“带”中。它是你能做出的最强渐近陈述，大致相当于 ==。 （抱歉，为了清楚起见，我选择将绝对值符号的提及推迟到现在；尤其是因为我从未见过在计算机科学环境中出现负值。）
人们经常会使用 = O(...)，这可能是更正确的“comp-sci”表示法，并且完全可以使用； “f = O(...)”读作“f is order ... / f is xxx-bounded by ...”并被认为是“f 是一些渐近线为 ...”的表达式。我被教导使用更严格的 ∈ O(...)。 ∈ 表示“是”的一个元素（仍然像以前一样阅读）。在这种特殊情况下，O(N²) 包含像 {2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} 这样的元素，并且是无限大的，但它是还是一套。 O 和 Ω 不是对称的（n = O(n²)，但 n² 不是 O(n)），但Ɵ 是对称的，并且（因为这些关系都是传递和自反的）Ɵ 因此是对称且传递和自反的，因此将所有函数的集合划分为等价类。等价类是我们认为相同的一组事物。也就是说，给定您能想到的任何函数，您都可以找到该类的规范/唯一“渐近代表”（通常取极限......我认为）；就像您可以将所有整数分组为奇数或偶数一样，您可以通过基本上忽略较小的术语将所有带有 Ɵ 的函数分组为 x-ish、log(x)^2-ish 等...更复杂的函数，它们本身就是独立的类）。
= 表示法可能是更常见的一种，甚至被世界著名的计算机科学家在论文中使用。此外，通常情况下，在随意的环境中，人们会说 O(...)，而他们的意思是 Ɵ(...)；这在技术上是正确的，因为这组事物 Ɵ(exactlyThis) 是 O(noGreaterThanThis) 的一个子集......而且它更容易输入。 ;-)
编辑：快速注意，这几乎肯定会将 Big O notation （这是一个上限）与 Theta 表示法（既是上限又是下限）混淆。以我的经验，这实际上是非学术环境中的典型讨论。对造成的任何混乱表示歉意。
一句话：随着你的工作规模越来越大，完成它需要多长时间？
显然，这只是使用“大小”作为输入，“所用时间”作为输出——如果你想谈论内存使用等，同样的想法也适用。
这是一个示例，我们有 N 件 T 恤要烘干。我们假设让它们处于干燥位置非常快（即人为交互可以忽略不计）。当然，现实生活中并非如此……
在外面使用晾衣绳：假设您有一个无限大的后院，洗涤物在 O(1) 时间内干燥。不管你有多少，它都会得到同样的阳光和新鲜空气，所以大小不会影响干燥时间。
使用滚筒式干衣机：您在每个负载中放入 10 件衬衫，然后它们在一个小时后完成。 （忽略这里的实际数字——它们无关紧要。）因此，烘干 50 件衬衫所需的时间大约是烘干 10 件衬衫所需时间的 5 倍。
把所有东西都放在一个晾晒的柜子里：如果我们把所有东西都放在一大堆里，让一般的温暖来做，中间的衬衫需要很长时间才能变干。我不想猜测细节，但我怀疑这至少是 O(N^2) - 随着洗涤负荷的增加，干燥时间增加得更快。
“大 O”表示法的一个重要方面是它没有说明对于给定大小哪种算法更快。采用哈希表（字符串键，整数值）与对数组（字符串，整数）。基于字符串在哈希表中查找键或数组中的元素是否更快？ （即对于数组，“找到字符串部分与给定键匹配的第一个元素。”）哈希表通常是摊销的（~=“平均”）O（1）——一旦它们被设置，它应该花费大约在 100 个条目表中查找条目与在 1,000,000 个条目表中查找条目的时间相同。在数组中查找元素（基于内容而不是索引）是线性的，即 O(N) — 平均而言，您将不得不查看一半的条目。
这是否使哈希表比查找数组更快？不必要。如果您有一个非常小的条目集合，那么数组可能会更快 - 您可以在计算您正在查看的字符串的哈希码所需的时间内检查所有字符串。然而，随着数据集变大，哈希表最终将击败数组。
Big O 描述了当输入变大时函数增长行为的上限，例如程序的运行时间。
例子：
O(n)：如果我将输入大小加倍，则运行时间加倍
O(n2)：如果输入大小翻倍，则运行时翻四倍
O(log n)：如果输入大小翻倍，则运行时间增加一
O(2n)：如果输入大小增加一，运行时间加倍
输入大小通常是表示输入所需的位空间。
程序员最常使用大 O 表示法作为计算（算法）完成所需时间的近似度量，表示为输入集大小的函数。
大 O 有助于比较两种算法随着输入数量的增加而扩展的程度。
更准确地说，Big O notation 用于表示函数的渐近行为。这意味着函数在接近无穷大时的行为方式。
在许多情况下，算法的“O”将属于以下情况之一：
O(1) - 无论输入集的大小如何，完成时间都是相同的。一个例子是通过索引访问数组元素。
O(Log N) - 完成时间大致与 log2(n) 一致。例如，1024 项大约是 32 项的两倍，因为 Log2(1024) = 10 和 Log2(32) = 5。一个例子是在二叉搜索树 (BST) 中查找一个项目。
O(N) - 完成时间与输入集的大小成线性关系。换句话说，如果您将输入集中的项目数加倍，则该算法大约需要两倍的时间。一个例子是计算链表中的项目数。
O(N Log N) - 完成时间增加的项目数乘以 Log2(N) 的结果。这方面的一个例子是堆排序和快速排序。
O(N^2) - 完成时间大致等于项目数的平方。这方面的一个例子是冒泡排序。
O(N!) - 完成时间是输入集的阶乘。这方面的一个例子是旅行商问题的蛮力解决方案。
随着输入大小向无穷大增加，Big O 忽略了对函数的增长曲线没有有意义的贡献的因素。这意味着简单地忽略添加到函数或乘以函数的常量。
Big O 只是一种以常见方式“表达”自己的方式，“运行我的代码需要多少时间/空间？”。
你可能经常会看到O(n)、O(n2)、O(nlogn)等等，这些只是展示的方式；算法如何变化？
O(n) 表示大 O 是 n，现在你可能会想，“n 是什么！？”那么“n”是元素的数量。成像您要在数组中搜索项目。您必须查看每个元素并作为“您是正确的元素/项目吗？”在最坏的情况下，该项目位于最后一个索引处，这意味着它花费的时间与列表中的项目一样多，所以为了通用，我们说“哦，嘿，n 是一个公平的给定数量的值！” .
那么您可能会理解“n2”的含义，但更具体地说，请考虑一下您有一个简单、最简单的排序算法；冒泡排序。该算法需要针对每个项目查看整个列表。
我的列表
6 3
这里的流程是：
比较 1 和 6，哪个最大？ Ok 6 位置正确，继续前进！
比较 6 和 3，哦，3 少了！让我们移动它，好吧，列表改变了，我们需要从头开始！
这是 O n2 因为，您需要查看列表中的所有项目，其中有“n”个项目。对于每个项目，你再看一遍所有项目，为了比较，这也是“n”，所以对于每个项目，你看“n”次，意思是 n*n = n2
我希望这和你想要的一样简单。
但请记住，Big O 只是一种以时空方式表达自己的方式。
Big O 描述了算法的基本缩放性质。
Big O 没有告诉你关于给定算法的很多信息。它切入骨干，仅提供有关算法缩放性质的信息，特别是算法的资源使用（思考时间或内存）如何响应“输入大小”而缩放。
考虑蒸汽机和火箭之间的区别。它们不仅是同一事物的不同品种（例如，普锐斯发动机与兰博基尼发动机），而且它们的核心是截然不同的推进系统。蒸汽机可能比玩具火箭快，但没有蒸汽活塞发动机能够达到轨道运载火箭的速度。这是因为这些系统在达到给定速度（“输入大小”）所需的燃料（“资源使用”）关系方面具有不同的缩放特性。
为什么这个这么重要？因为软件处理的问题的大小可能相差多达一万亿倍。考虑一下。前往月球所需的速度与人类步行速度之间的比率小于 10,000:1，与软件可能面临的输入大小范围相比，这绝对是微不足道的。并且由于软件可能面临输入大小的天文数字范围，因此算法的大 O 复杂性（它是基本的缩放性质）可能胜过任何实现细节。
考虑规范排序示例。冒泡排序是 O(n2)，而合并排序是 O(n log n)。假设您有两个排序应用程序，使用冒泡排序的应用程序 A 和使用合并排序的应用程序 B，假设对于大约 30 个元素的输入大小，应用程序 A 在排序时比应用程序 B 快 1,000 倍。如果您不必对超过 30 个元素进行排序，那么显然您应该更喜欢应用程序 A，因为在这些输入大小下它要快得多。但是，如果您发现您可能需要对一千万个项目进行排序，那么您所期望的是，在这种情况下，应用程序 B 实际上最终会比应用程序 A 快数千倍，这完全是由于每种算法的扩展方式。
这是我在解释 Big-O 的常见品种时倾向于使用的简单的英语动物寓言
在所有情况下，更喜欢列表中较高的算法而不是列表中较低的算法。但是，迁移到更昂贵的复杂性类别的成本差异很大。
O(1):
没有增长。无论问题有多大，您都可以在相同的时间内解决它。这有点类似于广播，在给定距离上广播需要相同数量的能量，而不管广播范围内有多少人。
O（日志n）：
这种复杂性与 O(1) 相同，只是稍微差一点。出于所有实际目的，您可以将其视为非常大的常数缩放。处理 1000 件和 10 亿件物品之间的工作差异仅为 6 倍。
上）：
解决问题的成本与问题的大小成正比。如果您的问题规模翻倍，那么解决方案的成本就会翻倍。由于大多数问题必须以某种方式扫描到计算机中，例如数据输入、磁盘读取或网络流量，因此这通常是一个负担得起的缩放因子。
O(n 日志 n):
这种复杂性与 O(n) 非常相似。出于所有实际目的，两者是等价的。这种复杂程度通常仍被认为是可扩展的。通过调整假设，一些 O(n log n) 算法可以转换为 O(n) 算法。例如，限制键的大小将排序从 O(n log n) 减少到 O(n)。
O(n2):
成长为一个正方形，其中 n 是正方形的边长。这与“网络效应”的增长率相同，网络中的每个人都可能认识网络中的其他人。增长是昂贵的。大多数可扩展的解决方案如果不做大量的练习，就无法使用这种复杂程度的算法。这通常也适用于所有其他多项式复杂性 - O(nk) - 。
O(2n):
不缩放。你没有希望解决任何非平凡的问题。对于知道要避免什么以及专家找到 O(nk) 中的近似算法很有用。
大 O 衡量算法相对于其输入大小使用了多少时间/空间。
如果算法是 O(n)，那么时间/空间将以与其输入相同的速率增加。
如果算法为 O(n2)，则时间/空间以其输入平方的速率增加。
等等。
衡量软件程序的速度是非常困难的，当我们尝试时，答案可能非常复杂，并且充满了异常和特殊情况。这是一个大问题，因为当我们想要将两个不同的程序相互比较以找出哪个“最快”时，所有这些异常和特殊情况都会分散注意力并且无益。
由于所有这些无益的复杂性，人们试图使用尽可能最小和最不复杂的（数学）表达式来描述软件程序的速度。这些表达式是非常粗略的近似：虽然，如果运气好的话，它们将捕捉到一个软件是快还是慢的“本质”。
因为它们是近似值，所以我们在表达式中使用字母“O”（Big Oh），作为一种约定，向读者表明我们过于简单化了。 （并确保没有人错误地认为表达式在任何方面都是准确的）。
如果您将“哦”理解为“大约”或“大约”的意思，那么您不会错得太远。 （我认为 Big-Oh 的选择可能是一种幽默的尝试）。
这些“Big-Oh”表达式试图做的唯一一件事就是描述当我们增加软件必须处理的数据量时软件减慢了多少。如果我们需要处理的数据量增加一倍，软件是否需要两倍的时间才能完成它的工作？十倍的时间？在实践中，您会遇到并且需要担心的大哦表达式数量非常有限：
好的：
O(1) 常数：无论输入有多大，程序都需要相同的时间来运行。
O(log n) 对数：程序运行时间仅缓慢增加，即使输入大小大幅增加。
坏处：
O(n) 线性：程序运行时间与输入的大小成比例增加。
O(n^k) 多项式： - 处理时间越来越快 - 作为多项式函数 - 随着输入大小的增加。
...和丑陋的：
O(k^n) 指数 程序运行时间增加得非常快，即使问题规模适度增加 - 只有用指数算法处理小数据集才可行。
O(n!) Factorial 程序运行时间将比你可以承受的时间更长，除了最小和最看似微不足道的数据集。
O(n log n) 这个词，它会被认为是好的。
Big O的简单英文解释是什么？尽可能少的正式定义和简单的数学。
需要 Big-O 表示法的简单英语解释：
当我们编程时，我们试图解决一个问题。我们编写的代码称为算法。大 O 表示法允许我们以标准化的方式比较算法的最坏情况性能。硬件规格随时间而变化，硬件的改进可以减少算法运行所需的时间。但是更换硬件并不意味着我们的算法会随着时间的推移变得更好或改进，因为我们的算法还是一样的。因此，为了让我们能够比较不同的算法，以确定一个是否更好，我们使用大 O 表示法。
Big O Notation 的简单英文解释：
并非所有算法都在相同的时间内运行，并且可能会根据输入中的项目数（我们将其称为 n）而有所不同。基于此，我们考虑最坏情况分析，或者当 n 越来越大时运行时间的上限。我们必须知道 n 是什么，因为许多大 O 符号都引用它。
好的，我的 2 美分。
Big-O，是程序消耗资源的增长率，wrt 问题实例大小
资源：可能是总 CPU 时间，可能是最大 RAM 空间。默认情况下是指 CPU 时间。
说问题是“求和”，
int Sum(int*arr,int size){
int sum=0;
while(size-->0)
sum+=arr[size];
return sum;
}
问题实例= {5,10,15} ==> 问题实例大小= 3，循环中迭代= 3
问题实例= {5,10,15,20,25} ==> 问题实例大小 = 5 循环中迭代 = 5
对于大小为“n”的输入，程序以数组中“n”次迭代的速度增长。因此 Big-O 是 N 表示为 O(n)
说问题是“找到组合”，
void Combination(int*arr,int size)
{ int outer=size,inner=size;
while(outer -->0) {
inner=size;
while(inner -->0)
cout<<arr[outer]<<"-"<<arr[inner]<<endl;
}
}
问题实例= {5,10,15} ==> 问题实例大小 = 3，总迭代次数 = 3*3 = 9
问题实例 = {5,10,15,20,25} ==> 问题实例大小 = 5，总迭代次数 = 5*5 =25
对于大小为“n”的输入，程序以数组中“n*n”次迭代的速度增长。因此 Big-O 是 N2 表示为 O(n2)
while (size-->0) 希望this不要再问了。
一个简单直接的答案可以是：
大 O 代表该算法可能出现的最差时间/空间。该算法永远不会占用超过该限制的更多空间/时间。大 O 代表极端情况下的时间/空间复杂度。
大 O 表示法是一种在空间或运行时间方面描述算法上限的方法。 n 是问题中元素的数量（即数组的大小、树中的节点数等）。我们感兴趣的是描述随着 n 变大的运行时间。
当我们说某个算法是 O(f(n)) 时，我们是在说该算法的运行时间（或所需空间）总是低于某个常数时间 f(n)。
说二分查找的运行时间为 O(logn) 就是说存在一些常数 c，你可以将它乘以 log(n) 总是大于二分查找的运行时间。在这种情况下，您将始终有一些 log(n) 比较的常数因子。
换句话说，其中 g(n) 是算法的运行时间，我们说 g(n) = O(f(n)) 当 g(n) <= c*f(n) 当 n > k 时，其中c 和 k 是一些常数。
“什么是大 O 的简单英语解释？尽可能少的正式定义和简单的数学。”
这样一个简单而简短的问题似乎至少应该得到一个同样简短的答案，就像学生在辅导期间可能会收到的一样。
大 O 表示法仅根据输入数据量** 告诉算法可以在多长时间内运行*。
（*在一种美妙的、无单位的时间感中！）
（**这很重要，因为人们会always want more，无论他们是今天还是明天）
好吧，如果 Big O 表示法就是这样做的，那么它有什么了不起的呢？
实际上，Big O 分析非常有用和重要，因为 Big O 将重点直接放在算法本身的复杂性上，并且完全忽略了任何仅仅是比例常数的东西——比如 JavaScript 引擎、CPU 的速度、您的 Internet 连接以及所有那些很快就变得像 T 型车一样过时的东西。Big O 只关注对生活在现在或未来的人们同样重要的性能。
大 O 表示法还直接聚焦计算机编程/工程最重要的原则，这一事实激励所有优秀的程序员不断思考和梦想：在技术缓慢前进的过程中取得成果的唯一方法是发明一个更好的算法。
算法示例（Java）：
public boolean search(/* for */Integer K,/* in */List</* of */Integer> L)
{
for(/* each */Integer i:/* in */L)
{
if(i == K)
{
return true;
}
}
return false;
}
算法说明：
该算法逐项搜索列表，寻找键，
迭代列表中的每个项目，如果它是键则返回 True，
如果循环结束但没有找到密钥，则返回 False。
Big-O 表示法表示复杂度的上限（时间、空间、..）
要找到关于时间复杂度的 Big-O：
计算最坏情况需要多少时间（关于输入大小）：
最坏情况：列表中不存在密钥。
时间（最坏情况）= 4n+1
时间：O(4n+1) = O(n) |在 Big-O 中，常数被忽略
O(n) ~ 线性
还有 Big-Omega，它代表了 Best-Case 的复杂性：
Best-Case：关键是第一项。
时间（最佳情况）= 4
时间：Ω(4) = O(1) ~ Instant\Constant
C 会更好
大 O 表示法是一种描述算法在给定任意数量的输入参数（我们将其称为“n”）的情况下运行速度的方式。它在计算机科学中很有用，因为不同的机器以不同的速度运行，仅仅说一个算法需要 5 秒并不能告诉你太多，因为虽然你可能正在运行一个具有 4.5 Ghz 八核处理器的系统，但我可能正在运行一个有 15 年历史的 800 Mhz 系统，无论算法如何，它都可能需要更长时间。因此，我们不是根据时间来指定算法运行的速度，而是根据输入参数的数量或“n”来说明它的运行速度。通过以这种方式描述算法，我们可以比较算法的速度，而不必考虑计算机本身的速度。
大O
f(x) = O(g(x)) 当 x 变为 a 时（例如，a = +∞）意味着有一个函数 k 满足：
f(x) = k(x)g(x) k 有界在 a 的某个邻域中（如果 a = +∞，这意味着存在数字 N 和 M 使得对于每个 x > N，|k(x) | < 米）。
换句话说，用简单的英语：f(x) = O(g(x)), x → a, 表示在 a 的邻域中，f 分解为 g 和某个有界函数的乘积。
小o
顺便说一下，这里是为了比较小o的定义。
f(x) = o(g(x)) 当 x 达到 a 意味着存在一个函数 k 使得：
当 x 变为 a 时，f(x) = k(x)g(x) k(x) 变为 0。
例子
当 x → 0 时 sin x = O(x)。
sin x = O(1) 当 x → +∞时，
x2 + x = O(x) 当 x → 0，
x2 + x = O(x2) 当 x → +∞时，
当 x → +∞ 时，ln(x) = o(x) = O(x)。
注意力！带有等号“=”的符号使用“假等式”：o(g(x)) = O(g(x)) 是真的，但 O(g(x)) = o(g （X））。类似地，可以写成“ln(x) = o(x) when x → +∞”，但公式“o(x) = ln(x)”就没有意义了。
更多示例
O(1) = O(n) = O(n2) 当 n → +∞ 时（但不是相反，等式是“假的”），
O(n) + O(n2) = O(n2) 当 n → +∞
O(O(n2)) = O(n2) 当 n → +∞
O(n2)O(n3) = O(n5) 当 n → +∞
这是维基百科的文章：https://en.wikipedia.org/wiki/Big_O_notation
你想知道关于大O的一切吗？我也是。
所以说到大O，我会用只有一个节拍的词。一字一音。小字很快。你知道这些词，我也知道。我们将使用一个声音的词。他们很小。我相信您会知道我们将使用的所有单词！
现在，让我们谈谈工作。大多数时候，我不喜欢工作。你喜欢工作吗？你可能会这样做，但我相信我不会。
我不喜欢去上班。我不喜欢把时间花在工作上。如果我有我的方式，我只想玩，做有趣的事情。你和我有同样的感觉吗？
现在有时，我确实必须去上班。这很可悲，但却是真实的。所以，当我在工作时，我有一个规则：我尽量少做一些工作。尽可能接近没有工作。那我去玩！
所以这里有一个大新闻：大O可以帮助我不工作！如果我知道大 O，我可以玩更多的时间。少工作，多玩！这就是大 O 帮助我做的事情。
现在我有一些工作。我有这个清单：一、二、三、四、五、六。我必须在此列表中添加所有内容。
哇，我讨厌工作。但是哦，好吧，我必须这样做。所以我来了。
一加二等于三……加三等于六……四等于……我不知道。我迷路了。在我的脑海里做这件事对我来说太难了。我不太喜欢这种工作。
所以我们不要做这项工作。让你和我想想这有多难。我需要做多少工作才能添加六个数字？
好吧，走着瞧。我必须加一和二，然后再加上三，然后再加上四……总而言之，我数了六。我必须做六个补充来解决这个问题。
大 O 来了，告诉我们这个数学有多难。
Big O 说：我们必须做六次加法来解决这个问题。加一，每件事从一到六。六小部分工作……每一部分工作都是一个加法。
好吧，我现在不做添加它们的工作。但我知道那会有多难。这将是六个添加。
哦不，现在我有更多的工作。嘘。这种东西谁做的？！
现在他们让我从一加到十！我为什么要这么做？我不想加一到六。从一加到十……嗯……那就更难了！
会有多难？我还需要做多少工作？我需要更多或更少的步骤吗？
好吧，我想我必须做十次加法……从一到十，每件事加一次。十大于六。从一到十，而不是从一到六，我必须做更多的工作！
我现在不想添加。我只是想想想添加这么多可能有多难。而且，我希望能尽快上场。
从一加到六，这是一些工作。但是你看，从一加到十，那是更多的工作吗？
Big O 是你的朋友，也是我的朋友。 Big O 帮助我们思考我们必须做多少工作，这样我们就可以计划。而且，如果我们是大O的朋友，他可以帮助我们选择不那么难的工作！
现在我们必须做新的工作。不好了。我一点也不喜欢这种工作。
新的工作是：将所有事物从一加到n。
等待！什么是n？我错过了吗？如果你不告诉我 n 是什么，我怎么能从一加到 n？
好吧，我不知道 n 是什么。我没有被告知。你是吗？不？那好吧。所以我们不能做这项工作。唷。
但是，虽然我们现在不做这项工作，但如果我们知道 n，我们可以猜测它会有多难。我们必须把 n 个东西加起来，对吧？当然！
现在大O来了，他会告诉我们这项工作有多难。他说：将所有事物从一加到 N，一一相加，是 O(n)。要添加所有这些东西，[我知道我必须添加 n 次。][1] 那是大 O！他告诉我们做某种工作有多难。
对我来说，我认为大 O 就像一个大而缓慢的老板。他想着工作，但他不去做。他可能会说，“那工作很快。”或者，他可能会说，“这项工作是如此缓慢而艰巨！”但他不做这项工作。他只是看着工作，然后告诉我们可能需要多长时间。
我很关心大O。为什么？我不喜欢工作！没有人喜欢工作。这就是为什么我们都喜欢大 O！他告诉我们可以多快地工作。他帮助我们思考工作有多辛苦。
哦，更多的工作。现在，让我们不要做这项工作。但是，让我们制定一个计划，一步一步地去做。
他们给了我们一副十张牌。它们都混在一起了：七、四、二、六……一点也不直。现在……我们的工作是对它们进行分类。
呃。听起来工作量很大！
我们如何分类这个牌组？我有个计划。
我会看每一对卡片，一对一对，从一副牌到最后一副。如果一对中的第一张牌很大，而该对中的下一张牌很小，我就交换它们。否则，我去下一对，依此类推……很快，套牌就完成了。
当套牌完成后，我问：我在那次传球中交换了牌吗？如果是这样，我必须从头再来一次。
在某些时候，在某些时候，不会有交换，我们的套牌就会完成。这么多工作！
那么，按照这些规则对卡片进行分类需要做多少工作？
我有十张卡片。而且，大多数时候——也就是说，如果我运气不好的话——我必须通过整副牌最多十次，每次翻牌最多十次。
大O，救救我！
大 O 进来并说：对于一副 n 牌，以这种方式排序将在 O(N 平方) 时间内完成。
为什么他说n平方？
嗯，你知道 n 的平方是 n 乘以 n。现在，我明白了：检查了 n 张牌，最多可以通过甲板 n 次。那是两个循环，每个循环有 n 个步骤。这是 n 平方很多工作要做。很多工作，当然！
现在当大 O 说它需要 O(n 平方) 工作时，他并不是说 n 平方相加，在鼻子上。在某些情况下，它可能会少一些。但在最坏的情况下，对甲板进行分类将需要接近 n 平方步的工作。
现在这里是大 O 是我们的朋友的地方。
Big O 指出了这一点：随着 n 变大，当我们对卡片进行分类时，这项工作比过去的只是添加这些东西的工作要困难得多。我们怎么知道呢？
好吧，如果 n 变得非常大，我们不在乎我们可能会添加到 n 或 n 平方。
对于大 n，n 的平方大于 n。
Big O 告诉我们，排序比添加更难。对于大 n，O(n squared) 大于 O(n)。这意味着：如果 n 变得非常大，那么对 n 个混合的东西进行排序必须花费更多的时间，而不是仅仅添加 n 个混合的东西。
Big O 并没有为我们解决工作。 Big O 告诉我们工作有多辛苦。
我有一副纸牌。我确实对它们进行了排序。你帮了忙。谢谢。
有没有更快的方法来分类卡片？大O可以帮助我们吗？
是的，还有更快的方法！学习需要一些时间，但它确实有效……而且效果非常快。您也可以尝试，但要花时间完成每一步，不要失去自己的位置。
在这种对牌组进行排序的新方法中，我们不会像之前那样检查成对的牌。以下是您对该套牌进行排序的新规则：
一：我在我们现在工作的牌组中选择一张牌。如果你愿意，可以给我选一个。 （我们第一次这样做时，“我们现在工作的套牌的一部分”当然是整个套牌。）
二：我在你选择的那张牌上展开套牌。这是什么展开；我怎么张开？好吧，我从起始牌一张一张地往下走，我寻找一张比张开牌更高的牌。
三：我从最后一张牌往上走，我寻找一张比张开牌低的牌。
找到这两张卡后，我将它们交换，然后继续寻找更多要交换的卡。也就是说，我回到第二步，在你选择的牌上再张开一些。
在某个时候，这个循环（从二到三）将结束。当搜索的两半在张开卡上相遇时，它就结束了。然后，我们刚刚用你在第一步中选择的牌张开了牌组。现在，所有靠近开始的牌都比张开牌低；接近尾端的牌比八字牌高。很酷的把戏！
四（这是有趣的部分）：我现在有两个小套牌，一个比 splay 卡低，一个比 splay 高。现在我去第一步，在每个小甲板上！也就是说，我从第一个小甲板上的第一步开始，当这项工作完成后，我从下一个小甲板上的第一步开始。
我把甲板分成几部分，对每一部分进行分类，越来越小，有时我没有更多的工作要做。现在这可能看起来很慢，有所有的规则。但相信我，它一点也不慢。这比第一种排序方法要少得多！
这种叫什么？它被称为快速排序！这种排序是由一个叫 C. A. R. Hoare 的人制作的，他称之为快速排序。现在，快速排序一直在使用！
快速排序将大牌分解成小牌。也就是说，它将大任务分解为小任务。
嗯。我想这里面可能有一个规则。要使大任务变小，请将它们分解。
这种方式相当快。多快？大 O 告诉我们：在平均情况下，这种排序需要 O(n log n) 的工作来完成。
它比第一种快还是快？大O，求救！
第一种是 O(n squared)。但是快速排序是 O(n log n)。你知道 n log n 小于 n 的平方，对于大 n，对吧？好吧，这就是我们知道快速排序速度快的原因！
如果你必须对牌组进行分类，最好的方法是什么？好吧，你可以做你想做的，但我会选择快速排序。
为什么选择快速排序？我当然不喜欢工作！我希望尽快完成工作。
我怎么知道快速排序的工作量更少？我知道 O(n log n) 小于 O(n squared)。 O 更小，因此快速排序的工作量更少！
现在你认识了我的朋友 Big O。他帮助我们减少工作量。如果你知道大 O，你也可以做更少的工作！
你和我一起学会了这一切！你真聪明！太感谢了！
现在工作完成了，我们去玩吧！
[1]：有一种作弊方法，一次将所有的东西从一加到n。一个名叫高斯的孩子在八岁时发现了这一点。不过我没那么聪明，所以don't ask me how he did it。
不确定我是否会进一步为该主题做出贡献，但仍然认为我会分享：我曾经发现 this blog post 有一些非常有用（虽然非常基本）的解释和关于大 O 的示例：
通过示例，这有助于将基本知识带入我的龟甲状头骨，所以我认为这是一个非常好的下降 10 分钟阅读，可以让你朝着正确的方向前进。
我有更简单的方法来理解时间复杂度，计算时间复杂度的最常用指标是大 O 表示法。这消除了所有常数因素，以便当 N 接近无穷大时，可以相对于 N 估计运行时间。一般来说，你可以这样想：
statement;
是恒定的。语句的运行时间不会相对于 N 改变
for ( i = 0; i < N; i++ )
statement;
是线性的。循环的运行时间与 N 成正比。当 N 加倍时，运行时间也加倍。
for ( i = 0; i < N; i++ )
{
for ( j = 0; j < N; j++ )
statement;
}
是二次方的。两个循环的运行时间与N的平方成正比。当N翻倍时，运行时间增加N * N。
while ( low <= high )
{
mid = ( low + high ) / 2;
if ( target < list[mid] )
high = mid - 1;
else if ( target > list[mid] )
low = mid + 1;
else break;
}
是对数的。算法的运行时间与 N 可以除以 2 的次数成正比。这是因为算法在每次迭代时将工作区域分成两半。
void quicksort ( int list[], int left, int right )
{
int pivot = partition ( list, left, right );
quicksort ( list, left, pivot - 1 );
quicksort ( list, pivot + 1, right );
}
是 N * log ( N )。运行时间由对数的 N 个循环（迭代或递归）组成，因此该算法是线性和对数的组合。
一般来说，对一维中的每个项目做某事是线性的，对二维中的每个项目做某事是二次的，将工作区域分成两半是对数的。还有其他大 O 度量，例如三次、指数和平方根，但它们并不常见。大 O 表示法被描述为 O ( ) 其中是度量。快速排序算法将被描述为 O ( N * log ( N ) )。
注意：这些都没有考虑到最佳、平均和最坏情况的措施。每个都有自己的大 O 符号。另请注意，这是一个非常简单的解释。 Big O 是最常见的，但也比我展示的更复杂。还有其他符号，例如大 omega、小 o 和大 theta。您可能不会在算法分析课程之外遇到它们。
查看更多：这里
假设我们正在讨论一个算法 A，它应该对大小为 n 的数据集做一些事情。
然后 O( <some expression X involving n> ) 用简单的英语表示：
如果您在执行 A 时不走运，则可能需要 X(n) 次操作才能完成。
碰巧的是，某些函数（将它们视为 X(n) 的 实现）往往会经常出现。这些是众所周知的并且易于比较（示例：1、Log N、N、N^2、N! 等。）
通过在谈论 A 和其他算法时比较这些，很容易根据算法可能（最坏情况）需要完成的操作数量对算法进行排名。
一般来说，我们的目标是找到或构造一个算法A，使其具有返回尽可能低的数字的函数X(n)。
如果您的脑海中有一个合适的无限概念，那么有一个非常简短的描述：
大 O 表示法告诉您解决无限大问题的成本。
此外
常数因素可以忽略不计
如果您升级到一台可以以两倍速度运行您的算法的计算机，那么大 O 表示法不会注意到这一点。常数因子的改进太小了，以至于在大 O 表示法所使用的范围内甚至都无法注意到。请注意，这是大 O 符号设计的有意部分。
然而，尽管可以检测到任何比常数因子“更大”的东西。
当有兴趣进行大小“大”到足以被视为近似无穷大的计算时，大 O 表示法大约是解决问题的成本。
如果以上没有意义，那么您的脑海中就没有一个兼容的直观的无限概念，您可能应该忽略以上所有内容；我所知道的使这些想法严谨的唯一方法，或者如果它们在直觉上还没有用，那么解释它们的唯一方法是首先教你大 O 符号或类似的东西。 （虽然，一旦你将来很好地理解了大 O 符号，可能值得重新审视这些想法）
假设您从亚马逊订购哈利波特：完整的 8 部电影合集 [蓝光]，并同时在线下载相同的电影合集。您想测试哪种方法更快。交付需要将近一天的时间，下载大约提前 30 分钟完成。伟大的！所以这是一场激烈的比赛。
如果我订购了《指环王》、《暮光之城》、《黑暗骑士三部曲》等多部蓝光电影，并同时在线下载所有电影怎么办？这一次，交付仍然需要一天才能完成，但在线下载需要3天才能完成。对于在线购物，购买商品（输入）的数量不影响交货时间。输出是恒定的。我们称之为 O(1)。
对于在线下载，下载时间与电影文件大小（输入）成正比。我们称之为 O(n)。
从实验中，我们知道在线购物比在线下载的规模更大。理解大 O 表示法非常重要，因为它可以帮助您分析算法的可扩展性和效率。
注意：大 O 表示法表示算法的最坏情况。假设 O(1) 和 O(n) 是上述示例的最坏情况。
参考：http://carlcheo.com/compsci
“Big O”符号的简单英文解释是什么？
非常快速的注意事项：
“Big O”中的 O 指的是“Order”（或准确地说是“order of”），因此您可以从字面上理解它用于订购某些东西以比较它们。
“大 O” 做了两件事： 估计您的计算机为完成一项任务而应用的方法的步骤数。促进与他人比较以确定其好坏的过程？ “Big O' 通过标准化的符号实现了上述两个目标。
估计您的计算机用于完成任务的方法的步骤数。
促进与他人比较以确定其好坏的过程？
“Big O' 通过标准化的符号实现了上述两个目标。
有七个最常用的符号 O(1)，表示您的计算机只需 1 步即可完成任务，非常好，Ordered No.1 O(logN)，表示您的计算机完成 logN 步的任务，很好，Ordered No. 2 O(N)，用N步完成任务，还算公平，3号订单O(NlogN)，用O(NlogN)步结束任务，不好，4号订单O(N^2)，用N^2步完成任务，很糟糕，5号订单O(2^N)，用2^N步完成任务，太可怕了，6号订单O(N！)，完成任务用 N 完成！步骤，太可怕了，7号订单
O(1)，表示您的计算机只需 1 步即可完成任务，非常好，已订购 1 号
O(logN)，表示你的电脑完成了一个 logN 步的任务，很好，Ordered No.2
O(N)，用 N 步完成任务，公平，订单号 3
O(NlogN)，以 O(NlogN) 步骤结束任务，不好，订单号 4
O(N^2)，用 N^2 步完成任务，这很糟糕，订单号 5
O(2^N)，用 2^N 步完成任务，太可怕了，6 号订单
O(N!)，用 N 完成任务！步骤，太可怕了，7号订单
https://i.stack.imgur.com/6zHEt.png
假设你得到符号 O(N^2)，你不仅清楚该方法需要 N*N 步来完成一项任务，而且从它的排名中你也可以看出它不如 O(NlogN)。
请注意行尾的顺序，以便您更好地理解。如果考虑所有可能性，则有超过 7 个符号。
在 CS 中，完成任务的一组步骤称为算法。在术语中，大 O 表示法用于描述算法的性能或复杂性。
此外，大 O 建立最坏情况或测量上界步骤。您可以参考 Big-Ω (Big-Omega) 以获得最佳情况。
Big-Ω (Big-Omega) notation (article) | Khan Academy
摘要“Big O”描述了算法的性能并对其进行了评估。或正式地解决它，“Big O”对算法进行分类并标准化比较过程。
定义：- 大 O 表示法是一种表示如果数据输入增加，算法性能将如何执行的表示法。
当我们谈论算法时，算法的输入、输出和处理有 3 个重要支柱。大 O 是符号表示法，它表示如果数据输入以何种速率增加，算法处理的性能会发生什么变化。
我建议您观看这段 youtube 视频，该视频通过代码示例深入解释了 Big O Notation。
https://i.stack.imgur.com/nuFCp.png
因此，例如假设一个算法需要 5 条记录，处理它们所需的时间是 27 秒。现在，如果我们将记录增加到 10，算法需要 105 秒。
简单来说，所花费的时间是记录数的平方。我们可以用 O(n ^ 2) 来表示。这种符号表示被称为大 O 符号。
现在请注意，单位可以是输入中的任何单位，可以是字节、位记录数，性能可以用任何单位来衡量，如秒、分钟、天等。所以它不是确切的单位，而是关系。
https://i.stack.imgur.com/ZnRL6.png
例如看下面的函数“Function1”，它接受一个集合并对第一条记录进行处理。现在，无论您放置 1000 、 10000 或 100000 条记录，此功能的性能都是相同的。所以我们可以用 O(1) 来表示它。
void Function1(List<string> data)
{
string str = data[0];
}
现在看下面的函数“Function2()”。在这种情况下，处理时间将随着记录数量的增加而增加。我们可以使用 O(n) 来表示该算法的性能。
void Function2(List<string> data)
{
foreach(string str in data)
{
if (str == "shiv")
{
return;
}
}
}
当我们看到任何算法的大 O 表示法时，我们可以将它们分为三类性能：-
日志和常量类别：- 任何开发人员都希望在此类别中看到他们的算法性能。线性：- 开发人员不希望看到此类别中的算法，直到其最后一个选项或仅剩的选项。指数：- 这是我们不想看到我们的算法并且需要返工的地方。
因此，通过查看大 O 表示法，我们对算法的好坏区域进行了分类。
https://i.stack.imgur.com/N2k4s.png
我建议你观看这个 10 分钟的视频，它使用示例代码讨论 Big O
https://www.youtube.com/watch?v=k6kxtzICG_g
最简单的查看方式（简单的英语）
我们试图了解输入参数的数量如何影响算法的运行时间。如果您的应用程序的运行时间与输入参数的数量成正比，则称它在 n 的大 O 中。
上述陈述是一个好的开始，但并不完全正确。
更准确的解释（数学）
认为
n=输入参数的数量
T(n)= 将算法的运行时间表示为 n 的函数的实际函数
c=一个常数
f(n)= 一个近似函数，将算法的运行时间表示为 n 的函数
那么就大 O 而言，只要以下条件为真，近似 f(n) 就被认为足够好。
lim T(n) ≤ c×f(n)
n→∞
当 n 接近无穷大时，方程被读取，n 的 T 小于或等于 n 的 c 乘以 f。
在大 O 表示法中，这写为
T(n)∈O(n)
这被读作 n 的 T 在 n 的大 O 中。
回到英语
根据上面的数学定义，如果你说你的算法是 n 的大 O，这意味着它是 n（输入参数的数量）或更快的函数。如果您的算法是 n 的大 O，那么它也自动是 n 平方的大 O。
n 的大 O 意味着我的算法运行速度至少和这个一样快。您不能查看算法的大 O 表示法并说它很慢。你只能说它很快。
查看 this 观看加州大学伯克利分校关于 Big O 的视频教程。这实际上是一个简单的概念。如果你听到 Shewchuck 教授（又名神级老师）解释它，你会说“哦，就是这样！”。
我找到了一个关于大 O 符号的非常好的解释，特别是对于一个不太喜欢数学的人。
https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
计算机科学中使用大 O 表示法来描述算法的性能或复杂性。 Big O 专门描述了最坏的情况，可用于描述算法所需的执行时间或使用的空间（例如在内存中或在磁盘上）。任何读过 Programming Pearls 或任何其他计算机科学书籍并且没有数学基础的人，当他们到达提到 O(N log N) 或其他看似疯狂的语法的章节时，都会碰壁。希望本文能帮助您了解大 O 和对数的基础知识。首先是程序员，其次是数学家（或者可能是第三或第四），我发现彻底理解 Big O 的最佳方法是在代码中生成一些示例。因此，以下是一些常见的增长顺序以及可能的描述和示例。 O(1) O(1) 描述了一种算法，无论输入数据集的大小如何，都将始终在相同的时间（或空间）中执行。 bool IsFirstElementNull(IList
这是一个非常简单的解释，但我希望它涵盖了最重要的细节。
假设您处理问题的算法取决于一些“因素”，例如让我们将其设为 N 和 X。
根据 N 和 X，您的算法将需要一些操作，例如在最坏的情况下它是 3(N^2) + log(X) 操作。
由于 Big-O 不太关心常数因子（也称为 3），因此您的算法的 Big-O 是 O(N^2 + log(X))。它基本上翻译了“您的算法在最坏情况下所需的操作量与此有关”。
关注公众号
不定期副业成功案例分享
