它显示了算法如何扩展。

上²）： 作为。。而被知道 二次复杂性

• 1项：1秒
• 10项：100秒
• 100项：10000秒

请注意，项目数增加了10倍，但时间增加了10倍²。基本上，n = 10，因此O（n²）给出了缩放因子n² 这是10²。

上）： 作为。。而被知道 线性复杂性

• 1项：1秒
• 10项：10秒
• 100项：100秒

这次项目数量增加了10倍，时间也增加了10倍。 n = 10，所以O（n）的比例因子是10。

O（1）： 作为。。而被知道 不断复杂

• 1项：1秒
• 10项：1秒
• 100项：1秒

项目数仍然增加10倍，但O（1）的比例因子始终为1。

O（log n）： 作为。。而被知道 对数复杂度

• 1项：1秒
• 10项：2秒
• 100项：3秒
• 1000项：4秒
• 10000项：5秒

计算次数仅增加输入值的对数。所以在这种情况下，假设每次计算需要1秒，输入的日志 n 因此，是所需的时间 log n。

这就是它的要点。他们减少了数学，所以它可能不完全是n² 或者他们说的是什么，但这将是缩放的主要因素。

Big-O表示法（也称为“渐近增长”表示法）是 当你忽略原点附近的常数因子和东西时，什么功能“看起来像”。我们用它来谈谈 事情如何规模。

基本

对于“足够”的大输入......

• f(x) ∈ O(upperbound) 手段 f “增长不快” upperbound
• f(x) ∈ Ɵ(justlikethis) 意思 f “长得很像” justlikethis
• f(x) ∈ Ω(lowerbound) 手段 f “增长不慢于” lowerbound

big-O表示法并不关心常数因素：函数 9x² 据说“长得很像” 10x²。大O也没有 渐近 符号关心 非渐近 东西（“原点附近的东西”或“当问题大小很小时会发生什么”）：该功能 10x² 据说“长得很像” 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 是最糟糕的处理器/内存使用情况“。

应用

作为纯粹的数学结构，big-O表示法不仅限于讨论处理时间和内存。您可以使用它来讨论缩放有意义的任何内容的渐近性，例如：

• 其中可能的握手次数 N 聚会的人（Ɵ(N²)特别是 N(N-1)/2但重要的是它“像”一样“ N²）
• 概率预期将某些病毒式营销视为时间函数的人数
• 网站延迟如何随CPU或GPU或计算机集群中的处理单元数量而变化
• CPU上的热量输出如何随晶体管数量，电压等而变化。
• 作为输入大小的函数，算法需要运行多长时间
• 作为输入大小的函数，算法需要运行多少空间

例

对于上面的握手示例，房间里的每个人都会震动其他人的手。在那个例子中， #handshakes ∈ Ɵ(N²)。为什么？

备份一点：握手的数量恰好是n-choose-2或 N*(N-1)/2 （N个人中的每个人都握着N-1其他人的手，但是这个双手握手因此除以2）：

但是，对于非常多的人来说，线性项 N 相形见绌并且有效地贡献了0（在图表中：随着参与者数量变大，对角线上空盒子的比例随总箱数变小）。因此缩放行为是 order N²，或握手的数量“像N²一样增长”。

#handshakes(N)
────────────── ≈ 1/2
     N²

就好像图表对角线上的空框（N *（N-1）/ 2复选标记）甚至不存在（N² 渐开线的勾选标记）。

（来自“普通英语”的临时题词:)如果你想向自己证明这一点，你可以在比率上执行一些简单的代数，将其分成多个术语（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 = 1百万，比率＃handshakes /x²：0.499999 ...

建立直觉

这让我们发表如......的陈述

“对于足够大的输入= N，无论常数因素如何，如果我 双 输入大小

编辑：快速说明，这几乎肯定令人困惑 大O符号 （带有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（log n）：如果输入大小加倍，则运行时间增加1

• O（2^ñ）：如果输入大小增加1，则运行时间加倍

输入大小通常是表示输入所需的位数。

程序员最常使用Big O表示法作为计算（算法）完成所需时间的近似度量，表示为输入集大小的函数。

Big O可用于比较两种算法随着输入数量的增加而扩展的程度。

更确切地说 大O符号 用于表示函数的渐近行为。这意味着函数在接近无穷大时的行为方式。

在许多情况下，算法的“O”将属于以下情况之一：

• O（1）  - 无论输入集的大小如何，完成时间都是相同的。一个例子是通过索引访问数组元素。
• O（Log N）  - 完成时间大致与log2（n）一致。例如，1024个项目大约需要32个项目的两倍，因为Log2（1024）= 10而Log2（32）= 5.一个例子是查找一个项目 二叉搜索树 （BST）。
• 上）  - 完成时间与输入集的大小成线性比例。换句话说，如果您将输入集中的项目数加倍，则算法大约需要两倍的时间。一个例子是计算链表中的项目数。
• O（N Log N）  - 完成时间增加项目数乘以Log2（N）的结果。一个例子是 堆排序 和 快速排序。
• O（N ^ 2）  - 完成时间大致等于项目数的平方。一个例子是 泡泡排序。
• 上！）  - 完成时间是输入集的阶乘。这方面的一个例子是 旅行推销员问题蛮力解决方案。

当输入大小朝向无穷大增加时，大O忽略了对函数的增长曲线没有有意义贡献的因素。这意味着简单地忽略了添加到函数或乘以函数的常量。

Big O只是一种以常见方式“表达”自己的方式，“运行我的代码需要多少时间/空间？”。

你可能经常看到O（n），O（n²），O（nlogn）等等，所有这些只是展示的方式;算法如何改变？

O（n）意味着大O是n，现在你可能会想，“什么是n！？” “n”是元素的数量。想要在阵列中搜索项目的图像。您必须查看每个元素并将其视为“您是正确的元素/项目吗？”在最坏的情况下，该项目位于最后一个索引，这意味着它花费的时间与列表中的项目一样多，因此为了通用，我们说“哦，嘿，n是一个公平的给定数量的值！” 。

那么你可能会理解“n²“意思是，但更具体地说，你会想到你有一个简单，最简单的排序算法; bubblesort。这个算法需要查看每个项目的整个列表。

我的列表

1. 1
2. 6
3. 3

这里的流程将是：

• 比较1和6，哪个最大？ Ok 6处于正确的位置，向前迈进！
• 比较6和3，哦，3更少！让我们移动一下，好的清单改变了，我们需要从现在开始！

这是哦² 因为，你需要查看列表中的所有项目都有“n”项。对于每个项目，您再次查看所有项目，为了进行比较，这也是“n”，因此对于每个项目，您看起来是“n”次，意味着n * n = n²

我希望这就像你想要的一样简单。

但请记住，Big O只是一种以时间和空间的方式表现自己的方式。

Big O描述了算法的基本缩放特性。

Big O没有告诉你有关给定算法的大量信息。它切入骨骼并仅提供有关算法的缩放特性的信息，特别是算法的资源使用（思考时间或内存）如何根据“输入大小”进行缩放。

考虑蒸汽机和火箭之间的区别。它们不仅仅是同一种物品的不同品种（例如，普锐斯发动机与兰博基尼发动机），但它们的核心是不同类型的推进系统。蒸汽机可能比玩具火箭更快，但没有蒸汽活塞发动机能够达到轨道运载火箭的速度。这是因为这些系统在达到给定速度（“输入尺寸”）所需的燃料关系（“资源使用”）方面具有不同的缩放特性。

为什么这个这么重要？因为软件处理的问题可能因数据大小不同而有所不同。考虑一下。前往月球所需的速度与人类步行速度之间的比率小于10,000：1，与软件可能面临的输入尺寸范围相比，这个比例非常小。而且由于软件可能面临输入大小的天文范围，因此算法的Big O复杂性可能会超越任何实现细节，这是基本的扩展性质。

考虑规范排序示例。冒泡排序是O（n²）merge-sort是O（n log n）。假设您有两个排序应用程序，即使用冒泡排序的应用程序A和使用合并排序的应用程序B，并且假设对于大约30个元素的输入大小，应用程序A在排序时比应用程序B快1,000倍。如果您不必排序超过30个元素，那么您应该更喜欢应用程序A，因为它在这些输入大小上要快得多。但是，如果您发现可能需要对1000万个项目进行排序，那么您所期望的是，在这种情况下，应用程序B实际上最终比应用程序A快数千倍，这完全取决于每种算法的扩展方式。

这是我在解释Big-O的常见变种时倾向于使用的普通英语动物

在所有情况下，首选列表中较高的算法列表中较低的算法。但是，迁移到更昂贵的复杂性类别的成本差别很大。

O（1）：

没有增长。无论问题有多大，您都可以在相同的时间内解决问题。这有点类似于广播，其中在给定距离上广播需要相同的能量，而不管广播范围内的人数。

O（日志 ñ）：

这种复杂性与之相同 O（1） 除了它只是有点糟糕。出于所有实际目的，您可以将其视为非常大的常量缩放。处理1千到10亿件物品之间的工作差异只是因素六。

O（ñ）：

解决问题的成本与问题的大小成正比。如果您的问题规模翻倍，那么解决方案的成本会翻倍。由于大多数问题必须以某种方式扫描到计算机中，如数据输入，磁盘读取或网络流量，这通常是一个负担得起的缩放因子。

O（ñ 日志 ñ）：

这种复杂性非常类似于 O（ñ）。出于所有实际目的，两者是等价的。这种复杂程度通常仍被认为是可扩展的。通过调整一些假设 O（ñ 日志 ñ） 算法可以转化为 O（ñ） 算法。例如，限制键的大小会减少排序 O（ñ 日志 ñ） 至 O（ñ）。

O（ñ²）：

成长为一个广场，在哪里 ñ 是正方形边长。这与“网络效应”的增长速度相同，网络中的每个人都可能知道网络中的其他人。增长是昂贵的。大多数可扩展的解决方案无法使用具有这种复杂程度的算法，而无需进行重要的体操。这通常适用于所有其他多项式复杂性 - O（ñ^ķ）  - 以及。

O（2^ñ）：

不规模。你没有希望解决任何非平凡的问题。有助于知道要避免什么，以及专家找到的近似算法 O（ñ^ķ）。