大O

f（x）=O（g（x））当x去a（例如， = +∞) 意味着有一个函数k：

1. f（x）=k（x）g（x）

2. k在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：

1. f（x）=k（x）g（x）

2. k（x）当x变为a时变为0。

示例

• sin x=O（x）当x→0。

• sin x=O（1）当x→+∞，

• x²+x=O（x）当x→0时，

• x²+x=O（x²）当x→+∞，

• ln（x）=o（x）=O（x）当x→+∞。

注意！带有等号“=”的符号使用了“假等式”：o（g（x））=O（g（x））是真的，但O（g（x））=o（g（x））是假的。类似地，当x时写“ln（x）=o（x） → +∞", 但公式“o（x）=ln（x）”没有意义。

更多示例

• O（1）=O（n）=O（n²）当n → +∞ (但不是相反，等式是“假”），

• O（n）+O（n²）=O（n²）当n→+∞

• O（O（n²））=O（n²）当n→+∞

• O（n²）O（n³）=O（n⁵）当n→+∞

这是维基百科的文章：https://en.wikipedia.org/wiki/Big_O_notation

算法示例（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，它代表了最佳案例的复杂性：

• 最佳情况：关键是第一项。

• 时间（最佳情况）=4

• 时间：Ω（4）=O（1）~瞬间\常数

衡量软件程序的速度是非常困难的，当我们尝试时，答案可能非常复杂，充满了异常和特殊情况。这是一个大问题，因为当我们想将两个不同的程序相互比较以找出哪个“最快”时，所有这些异常和特殊情况都会分散注意力并且无济于事。

由于所有这些无益的复杂性，人们试图使用尽可能最小和最不复杂的（数学）表达式来描述软件程序的速度。这些表达式是非常非常粗略的近似：尽管，如果运气好的话，它们将抓住一个软件是快还是慢的“本质”。

因为它们是近似值，我们在表达式中使用字母“O”（Big Oh），作为一种惯例，向读者表明我们正在进行严重的过度简化（并确保没有人错误地认为表达式在任何方面都是准确的）。

如果你把“Oh”读成“on the order of”或“大约”的意思，你就不会错得太远。（我认为选择大Oh可能是一种幽默的尝试）。

这些“Big-Oh”表达试图做的唯一事情是描述当我们增加软件必须处理的数据量时，软件会减慢多少。如果我们需要处理的数据量增加一倍，软件是否需要两倍的时间来完成它的工作？十倍的时间？在实践中，你会遇到并且需要担心的Big-Oh表达数量非常有限：

好的方面：

• O(1)恒定：无论输入有多大，程序都需要相同的时间来运行。
• O(log n)对数：程序运行时的增加速度很慢，即使输入的大小大大增加。

坏处：

• O(n)线性：程序运行时与输入的大小成比例增加。
• O(n^k)多项式：处理时间增长越来越快-作为多项式函数-随着输入大小的增加。

和丑陋的：

• O(k^n)指数程序运行时间增长非常快，即使问题的大小适度增加-只有使用指数算法处理小数据集才实用。
• O(n!)阶乘程序运行时间将超过您等待任何东西的时间，除了最小和最琐碎的数据集。

"什么是大O的简单英语解释？尽可能简单的数学定义。"

这样一个美丽简单而简短的问题似乎至少应该得到一个同样简短的答案，就像学生在辅导期间可能得到的那样。

大O符号简单地告诉算法可以在多长时间内运行，只有输入数据量**

（*在美妙的时间感中！）
（**这很重要，因为人们会总是想要更多，不管他们活在今天还是明天）

好吧，大O符号有什么好的，如果它是这样做的？

• 实际上，大O分析是非常有用和重要的，因为大O直接将焦点放在算法自身的复杂性上，而完全忽略了任何只是比例常数的东西，比如JavaScript引擎、中央处理器的速度、你的互联网连接，以及所有那些很快就会像模型T一样可笑地过时的东西。大O只关注对生活在现在和未来的人同样重要的性能。

• 大O符号也直接聚焦于计算机编程/工程最重要的原则，这一事实激励所有优秀的程序员不断思考和梦想：超越技术缓慢前进的唯一方法是发明更好的算法。

假设我们正在谈论一个算法一个，它应该对大小为n的数据集做一些事情。

那么O( <some expression X involving n> )用简单的英语表示：

如果你在执行A时运气不好，它可能需要尽可能多的X（n）操作才能执行完成。

碰巧的是，有一些函数（把它们想象成X（n）中的实现）往往经常出现。这些是众所周知的，很容易比较（例如：1、Log N、N、N^2、N!等…）

在讨论一个和其他算法时，通过比较这些算法，很容易根据它们可能（最坏情况）需要完成的操作数量对算法进行排名。

一般来说，我们的目标是找到或构造算法一个，使其具有返回尽可能低的数字的函数X(n)。

一个简单直接的答案可以是：

大O代表该算法最糟糕的时间/空间。该算法永远不会占用超过该限制的更多空间/时间。大O在极端情况下代表时间/空间复杂度。

这是我在解释Big-O的常见变种时倾向于使用的简单英语动物寓言集

在所有情况下，更喜欢列表中较高的算法而不是列表中较低的算法。然而，迁移到更昂贵的复杂性类的成本差异很大。

O（1）：

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

O（logn）：

这种复杂性与O（1）相同，只是稍微差了一点。出于所有实际目的，您可以将其视为一个非常大的常量缩放。处理1000和10亿项之间的工作差异仅为6倍。

O（n）：

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

O（nlogn）：

这种复杂度与O（n）非常相似。出于所有实际目的，两者是等价的。这种复杂度通常仍被认为是可扩展的。通过调整假设，一些O（nlogn）算法可以转换为O（n）算法。例如，限制键的大小将排序从O（nlogn）减少到O（n）。

O（n²）：

增长为正方形，其中n是正方形边长。这与“网络效应”的增长率相同，网络中的每个人可能都认识网络中的其他人。增长是昂贵的。大多数可扩展的解决方案无法使用这种复杂程度的算法，而不做大量的练习。这通常适用于所有其他多项式复杂性-O（n^k）-也是。

O（2ⁿ）：

无法扩展。您没有希望解决任何不重要的问题。对于知道要避免什么以及专家找到O（n^k）中的近似算法很有用。

大O表示法是一种描述给定任意进审量参数的算法运行速度的方法，我们称之为“n”。它在计算机科学中很有用，因为不同的机器以不同的速度运行，简单地说算法需要5秒并不能告诉你很多，因为当你运行一个具有4.5 Ghz八核处理器的系统时，我可能运行一个15年前的800 Mhz系统，无论算法如何，这可能需要更长的时间。因此，我们没有指定算法在时间上的运行速度，而是用进审量参数或“n”来表示它的运行速度。通过以这种方式描述算法，我们能够比较算法的速度，而无需考虑计算机本身的速度。

我有更简单的方法来理解时间复杂度计算时间复杂度的最常见度量是Big 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个对数循环（迭代或递归）组成，因此该算法是线性和对数的组合。

一般来说，用一维中的每个项目做某事是线性的，用二维中的每个项目做某事是二次的，将工作区域分成两半是对数的。还有其他Big O度量，如立方、指数和平方根，但它们并不那么常见。Big O表示法被描述为O（）在哪里是度量。快速排序算法将被描述为O（N*log（N））。

注意：所有这些都没有考虑最佳，平均和最坏情况的度量。每个都有自己的Big O符号。还要注意，这是一个非常简单的解释。Big O是最常见的，但它也更复杂，我已经展示过了。还有其他的符号，例如大ω，小o和大θ。你可能在算法分析课程之外不会遇到它们。

• 查看更多：这里

如果你脑子里有一个合适的无穷大概念，那么有一个非常简短的描述：

大O表示法告诉你解决一个无穷大问题的成本。

此外，还有

常数可以忽略不计

如果你升级到一台可以以两倍的速度运行算法的计算机，大O符号不会注意到这一点。常数因子改进太小，甚至在大O符号工作的规模中都不会注意到。请注意，这是大O符号设计的有意部分。

然而，尽管可以检测到任何比常数因子“更大”的东西。

当对计算的大小“大”到足以被认为是近似无穷大感兴趣时，大O符号大约是解决问题的成本。

如果以上没有意义，那么你的头脑中就没有一个兼容的直觉无穷大概念，你可能应该忽略上述所有内容；我知道的唯一使这些想法严谨的方法，或者解释它们，如果它们还没有直观地有用，是首先教你大O符号或类似的东西。

如果我想向6岁的孩子解释这一点，我会开始画一些函数f（x）=x和f（x）=x^2，例如，并问孩子哪个函数将是页面顶部的上层函数。然后我们将继续绘图，看到x^2获胜。“谁赢了”实际上是当x趋向无穷大时增长更快的函数。所以“函数x在x^2的大O中”意味着当x趋向无穷大时，x的增长速度比x^2慢。当x趋向于0时也可以这样做。如果我们为x从0到1绘制这两个函数，x将是一个上函数，所以“函数x^2在x的大O中，因为x趋向于0”。当孩子长大后，我补充说，真正的大O可以是一个函数，它的增长速度不是更快，而是与给定函数相同。此外，常量被丢弃。所以2x在x的大O中。

最简单的方式来看待它（用简单的英语）

我们试图看看进审量参数如何影响算法的运行时间。如果应用程序的运行时间与进审量参数成正比，那么它被称为n的大O。

上述说法是一个好的开始，但并不完全正确。

更准确的解释（数学）

假设

n=进审量参数

T（n）=表示算法运行时间为n的函数的实际函数

c=常数

f（n）=表示算法运行时间为n的函数的近似函数

那么就大O而言，只要下面的条件为真，近似f（n）就被认为足够好。

lim     T(n) ≤ c×f(n)n→∞

等式读作当n接近无穷大时，n的T小于或等于c乘以n的f。

在大O符号中，这写为

T(n)∈O(n)

这读为T of n是n的大O。

返回英文

根据上面的数学定义，如果你说你的算法是n的大O，这意味着它是n（进审量参数）或更快的函数。如果你的算法是n的大O，那么它也自动是n平方的大O。

n的大O意味着我的算法运行至少和这个一样快。你不能看着你算法的大O符号说它慢。你只能说它快。

看看加州大学伯克利分校关于Big O的视频教程。这实际上是一个简单的概念。如果你听到Shewchuck教授（又名上帝级教师）解释它，你会说“哦，这就是全部！”。

这是一个非常简单的解释，但我希望它涵盖了最重要的细节。

假设您处理问题的算法取决于一些“因素”，例如，让我们将其设为N和X。

根据N和X，你的算法将需要一些操作，例如在最坏的情况下，它是3(N^2) + log(X)操作。

由于Big-O不太关心常数因子（也就是3），所以你的算法的Big-O是O(N^2 + log(X))。它基本上转换为“你的算法在最坏情况下需要的运算量”。

假设您从亚马逊订购了《哈利·波特：完整的8部电影合集》[蓝光]，并同时在线下载了相同的电影合集。您想测试哪种方法更快。交付几乎需要一天才能到达，下载大约提前30分钟完成。太好了！所以这是一场紧张的比赛。

如果我订购几部蓝光电影，如《指环王》、《暮光之城》、《黑暗骑士三部曲》等，并同时在线下载所有电影怎么办？这次，交付仍然需要一天才能完成，但在线下载需要3天才能完成。对于网上购物，购买的商品数量（输入）不会影响交货时间。输出是恒定的。我们称之为O（1）。

对于在线下载，下载时间与电影文件大小（输入）成正比。我们称之为O（n）。

从实验中，我们知道在线购物比在线下载更好。理解大O符号非常重要，因为它可以帮助您分析算法的扩展性和效率。

备注： Big O表示算法的最坏的情况。让我们假设O（1）和O（n）是上面示例的最坏情况。

参考：http://carlcheo.com/compsci

你想知道所有关于大O的事吗？我也是。

所以说到大O，我将使用只有一个节拍的单词。每个单词一个音。小词很快。你知道这些单词，我也知道。我们将使用一个音的单词。它们很小。我相信你会知道我们将使用的所有单词！

现在，我们来谈谈工作。大多数时候，我不喜欢工作。你喜欢工作吗？你可能喜欢，但我肯定我不喜欢。

我不喜欢去工作。我不喜欢花时间在工作上。如果我有我的方式，我只想玩，做有趣的事情。你和我的感觉一样吗？

有时候，我确实得去工作。这很悲伤，但却是事实。所以，当我在工作的时候，我有一个规则：我尽量少做工作。尽可能地接近没有工作。然后我去玩！

所以这里有个大新闻：大O可以帮助我不工作！如果我知道大O，我可以更多的时间玩。少工作，多玩！这就是大O帮助我做的。

现在我有一些工作要做。我有一张单子：一、二、三、四、五、六。我必须把这张单子上的所有东西都加起来。

哇，我讨厌工作。但是哦，好吧，我必须这样做。所以我走了。

一加二是三……加三是六……四是……我不知道。我迷路了。这对我来说太难了。我不太喜欢这种工作。

所以我们不要做这些工作。让我们想想这有多难。我需要做多少工作，把六个数字相加？

好吧，让我看看。我必须把1和2相加，然后把它加到3，然后把它加到4……总而言之，我数了6个加法。我必须做6个加法来解决这个问题。

大O来了，告诉我们这个数学有多难。

大O说：我们必须做六个加法来解决这个问题。一个加法，从一到六的每一件事。六个小块工作…每一点工作都是一个加法。

好吧，我现在不会做添加它们的工作。但我知道这有多难。这将是六个添加。

哦，不，现在我有更多的工作了。哎呀。谁做这种东西？！

现在他们让我从一加到十！我为什么要这么做？我不想加一到六。从一加到十……嗯……那就更难了！

这会有多难？我还需要做多少工作？我需要更多还是更少的步骤？

嗯，我想我得做十次加法…从一到十，每次加一次。十比六还多。我得做更多的工作才能从一加到十，而不是从一加到六！

我现在不想补充。我只是想知道增加这么多可能有多难。而且，我希望，尽快参加比赛。

从一加到六，这是一些工作。但是你看，从一加到十，这是更多的工作吗？

大O是你我的朋友。大O帮助我们思考我们有多少工作要做，这样我们就可以计划。而且，如果我们和大O是朋友，他可以帮助我们选择不那么难的工作！

现在我们必须做新的工作。哦，不。我一点也不喜欢这个工作。

新的工作是：将所有从1到n的东西相加。

等等！n是什么？我错过了吗？如果你不告诉我n是什么，我怎么能从一到n相加？

嗯，我不知道n是什么。我没有被告知。是吗？没有？哦，好吧。所以我们不能做这项工作。呼。

但是，虽然我们现在不做这项工作，但我们可以猜到，如果我们知道n，我们将不得不把n件事加起来，对吗？当然！

现在大O来了，他会告诉我们这项工作有多难。他说：把所有的东西从1到N，一个接一个，是O（n）。要把所有这些东西加起来，[我知道我必须加n次。][1]这是大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大。

大O告诉我们排序比添加东西更难。对于大n，O（n平方）大于O（n）。这意味着：如果n变得非常大，对n个混合的东西进行排序必须花费更多的时间，而不仅仅是添加n个混合的东西。

大O并不能为我们解决工作。大O告诉我们工作有多难。

我有一副牌。我把它们分类了。你帮了忙。谢谢。

有没有更快的方法来分类卡片？大O能帮我们吗？

是的，还有一种更快的方法！学习需要一些时间，但它有效……而且效果相当快。你也可以试试，但每一步都要慢慢来，不要失去你的位置。

在这种对一副牌进行排序的新方法中，我们不像以前那样检查牌对。这是您对这副牌进行排序的新规则：

一：我在我们现在使用的部分牌组中选择一张牌。如果你愿意，你可以为我选择一张。（我们第一次这样做时，“我们现在使用的部分牌组”当然是整个牌组。）

第二：我在你选择的那张牌上张开甲板。这张牌是什么？我怎么张开？好吧，我从开始牌开始，一张接一张，我寻找一张比张牌更高的牌。

第三：我从底牌往上走，寻找一张比斜板更低的牌。

一旦我找到了这两张牌，我就交换它们，然后继续寻找更多的牌来交换。也就是说，我回到第二步，在你选择的牌上展开。

在某个时候，这个循环（从二到三）将结束。当这个搜索的两半在张纸牌相遇时，它就结束了。然后，我们刚刚用你在第一步中选择的牌张开了甲板。现在，开始附近的所有牌都比张纸牌低；靠近结尾的牌比张纸牌高。酷技巧！

四（这是有趣的部分）：我现在有两个小甲板，一个比斜板低，一个高。现在我去第一步，在每个小甲板上！也就是说，我从第一个小甲板上的第一步开始，当这项工作完成后，我从下一个小甲板上的第一步开始。

我把甲板分成几部分，然后对每一部分进行排序，越来越小，越来越小，有时我没有更多的工作要做。现在这可能看起来很慢，有所有的规则。但是相信我，它一点也不慢。它比第一种排序方法要少得多！

这种排序叫什么？它叫做快速排序！这种排序是由一个叫C. A. R. Hoare的人做的，他称之为快速排序。现在，快速排序一直在使用！

快速排序将大任务分解为小任务。也就是说，它将大任务分解为小任务。

嗯。我想这里面可能有一条规则。把大任务变小，把它们分开。

这种排序相当快。有多快？Big O告诉我们：在平均情况下，这种排序需要O（n log n）个工作来完成。

它比第一种排序快还是慢？大O，请帮忙！

第一个排序是O（n平方）。但是快速排序是O（n log n）。你知道n log n小于n平方，对于大n，对吧？好吧，这就是我们知道快速排序快的原因！

如果你必须对甲板进行排序，最好的方法是什么？嗯，你可以做你想做的，但我会选择快速排序。

我为什么选择快速排序？当然，我不喜欢工作！我想尽快完成工作。

我怎么知道快速排序的工作量更少？我知道O（n log n）小于O（n平方）。O更小，所以快速排序的工作量更少！

现在你知道我的朋友，大O。他帮助我们做更少的工作。如果你知道大O，你也可以做更少的工作！

你跟我一起学的！你太聪明了！太谢谢你了！

工作结束了，我们去玩吧！

[1]：有一种方法可以作弊，一次把从1到n的所有东西都加起来。一个叫高斯的孩子在他八岁的时候发现了这一点。虽然我没有那么聪明，所以别问我他是怎么做到的。

简单地说，大O就像<=（小于或等于）。当我们说两个函数f和g时，f=O（g）意味着f<=g。

然而，这并不意味着对于任何n f（n）<=g（n）。实际上它的意思是f在增长方面小于或等于g。它意味着在某一点之后 f（n）<=c*g（n）ifc是常数。在某一点之后意味着比所有n>=n0其中n0是另一个不变。

大O是表示任何函数上界的一种手段。我们通常用它来表示告诉算法运行时间的函数的上界。

例如：f（n）=2（n^2）+3n是一个代表假设算法运行时间的函数，Big-O符号本质上给出了这个函数的上限，即O（n^2）

这个符号基本上告诉我们，对于任何输入'n'，运行时间都不会大于Big-O符号表示的值。

另外，同意以上所有详细的答案。希望这有助于！！

Big O描述了一类函数。

它描述了函数对于大输入值的增长速度。

对于给定的函数f，O（f）对所有可以找到n0和常量c的函数g（n）进行描述，使得n>=n0的g（n）的所有值都小于或等于c*f（n）

在较少的数学单词中，O（f）是一组函数。即所有函数，从某个值n0开始，增长速度慢或与f一样快。

如果f（n）=n，则

g（n）=3n在O（f）中。因为常数因子无关紧要h（n）=n+1000在O（f）中，因为对于小于1000的所有值，它可能更大，但对于大O，只有巨大的输入才重要。

然而，i（n）=n^2不在O（f）中，因为二次函数比线性函数增长得更快。

我找到了一个关于大O符号的非常好的解释，特别是对于一个不太喜欢数学的人。

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

计算机科学中使用大O表示法来描述性能或算法的复杂性。Big O特别描述了最坏的情况，可用于描述执行时间所需或使用的空间（例如在内存或磁盘上）算法

任何读过《编程珍珠》或任何其他计算机科学的人没有数学基础的书就会碰壁当他们到达提到O（N log N）或其他看似疯狂的语法。希望这篇文章能帮助你获得一个了解大O和对数的基础知识。

首先是程序员，其次是数学家（或者第三或第三我发现彻底理解Big O的最好方法是在代码中生成一些示例。所以，下面是一些常见的顺序在可能的情况下加上描述和例子。

O（1）

O（1）描述了一个总是在同一时间执行的算法（或空间）而不管输入数据集的大小。

bool IsFirstElementNull(IList<string> elements) {return elements[0] == null;}

O（N）

O（N）描述了一种算法，其性能将线性增长与输入数据集的大小成正比。示例下面还展示了Big O如何偏爱最坏的情况场景；在任何迭代期间都可以找到匹配的字符串for循环，函数会提前返回，但Big O符号会始终假设算法将执行的上限最大迭代次数。

bool ContainsValue(IList<string> elements, string value) {foreach (var element in elements){if (element == value) return true;}
return false;}

O（N²）

O（N²）表示一种算法，其性能直接与输入数据集大小的平方成正比。这是与涉及数据嵌套迭代的算法常见设置。更深的嵌套迭代将导致O（N³）、O（N⁴）等。

bool ContainsDuplicates(IList<string> elements) {for (var outer = 0; outer < elements.Count; outer++){for (var inner = 0; inner < elements.Count; inner++){// Don't compare with selfif (outer == inner) continue;
if (elements[outer] == elements[inner]) return true;}}
return false;}

O（2^N）

O（2^N）表示一个算法，其增长与每个附加值翻倍输入数据集。O（2^N）函数的增长曲线为指数-开始非常浅，然后迅速上升。一个O（2^N）函数的例子是斐波那契的递归计算数字：

int Fibonacci(int number) {if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);}

对数

对数解释起来有点棘手，所以我将使用一个通用的示例：

二进制搜索是一种用于搜索排序数据集的技术通过选择数据集的中间元素，本质上是中位数，并将其与目标值进行比较。如果值匹配将返回成功。如果目标值高于探测元素将占据数据集的上半部分对其执行相同的操作。同样，如果目标值低于它将执行的探测元素的值对下半部进行操作。它将继续将数据减半设置每次迭代，直到找到值或直到它可以不再分割数据集。

这种类型的算法被描述为O（log N）二进制搜索示例中描述的数据集会产生增长曲线在开始时达到峰值，然后随着大小逐渐变平的数据集增加，例如包含10个项目的输入数据集完成需要一秒钟，包含100个项目的数据集需要2秒，包含1000个项目的数据集需要3秒将输入数据集的大小加倍对它的增长是在算法的一次迭代之后将减半，因此与输入数据集相当大小。这使得像二分搜索这样的算法非常有效在处理大型数据集时。

前言

算法：解决问题的过程/公式

如何分析算法以及我们如何将算法相互比较？

例子：要求你和一个朋友创建一个函数来求和从0到N的数字。你想出f（x），你的朋友想出g（x）。两个函数的结果相同，但算法不同。为了客观地比较我们使用大O符号算法的效率。

Big-O符号：描述随着输入变得任意大，运行时相对于输入的增长速度。

3关键收获：

1. 比较运行时的增长速度不是比较精确运行时间（取决于硬件）
2. 只关心相对于输入（n）的运行时增长
3. 当n变得任意大时，专注于随着n变大而增长最快的项（想想无穷大）AKA渐近分析

空间复杂度：除了时间复杂度，我们还关心空间复杂度（算法使用多少内存/空间）。我们不是检查操作的时间，而是检查内存分配的大小。

大O-经济观点。

我最喜欢的英语单词来描述这个概念是价格，你为一个任务支付，因为它变得更大。

把它看作是经常性成本，而不是你在开始时支付的固定成本。在大局中，固定成本变得可以忽略不计，因为成本只会增长，而且会增加。我们想衡量它们增长的速度和它们增加的速度，以及我们为问题的设置-规模提供的原材料。

但是，如果初始设置成本很高，并且您只生产少量产品，则需要查看这些初始成本-它们也称为常数。

因为从长远来看，这些常量并不重要，所以这种语言允许我们讨论任务，而不仅仅是我们在什么样的基础设施上运行它。所以，工厂可以在任何地方，工人可以是任何人——这都是肉汁。但从长远来看，随着你的投入和产出的增长，工厂的规模和工人的数量是我们可以改变的。

因此，这就变成了你需要花多少钱来运行某件事情的大图近似。由于时间和空间是这里的经济数量（即它们是有限的），它们都可以用这种语言来表达。

技术说明：一些时间复杂度的例子——O（n）通常意味着如果问题的大小为“n”，我至少必须看到所有内容。O（log n）通常意味着我将问题的大小减半，并检查和重复，直到任务完成。O（n^2）意味着我需要查看成对的事物（比如n人之间的聚会握手）。

什么是“大O”符号的简单英语解释？

快速备注：

“大O”中的O指的是“Order”（或准确地说“order of”）
所以你可以从字面上得到它的想法，它是用来订购一些东西来比较它们的。

• “大O”做两件事：

  1. 估计您的计算机应用该方法来完成任务的步骤数。
  2. 促进与他人进行比较的过程，以确定它是否好？
  3. “Big O”通过标准化Notations实现了上述两个。

• 有七个最常用的符号

  1. O（1），表示您的计算机以1步完成任务，非常出色，订购号
  2. O（logN），表示您的计算机以logN步完成任务，很好，排序为2
  3. O（N），用N步完成任务，它是公平的，订单号3
  4. O（NlogN），以O(NlogN)步结束任务，不好，订单4
  5. O（N^2），用N^2步完成任务，很糟糕，订单号5
  6. O（2^N），用2^N步完成任务，太可怕了，订单号6
  7. O（N！），用N!步完成任务，太可怕了，订单号7

假设你得到符号O(N^2)，不仅你清楚该方法需要N*N个步骤来完成任务，而且你会发现它的排名不如O(NlogN)。

请注意行尾的顺序，以便您更好地理解。

在CS中，完成任务的一组步骤称为算法。
在术语中，Big O表示法用于描述算法的性能或复杂性。

此外，Big O建立最坏情况或测量上限步骤。
您可以参考Big-Ω（Big-Omega）以获得最佳情况。

大Ω（大欧米茄）符号（文章）|可汗学院

• 总结
  "Big O"描述算法的性能并对其进行评估。

  或者正式地解决它，“Big O”对算法进行分类并标准化比较过程。

TLDR：Big O用数学术语解释算法的性能。

较慢的算法倾向于以n的x次方运行，或者很多，这取决于它的深度。而更快的算法，如二分搜索，运行在O（log n），这使得它随着数据集变得更大而运行得更快。大O可以用其他使用n的术语来解释，甚至不使用n（即： O（1））。

人们可以计算Big O查看算法中最复杂的线条。

对于较小或未排序的数据集，Big O可能会令人惊讶，因为像二分搜索这样的n log n复杂性算法对于较小或未排序的集合可能会很慢，对于线性搜索与二分搜索的简单运行示例，请看我的JavaScript示例：

https://codepen.io/serdarsenay/pen/XELWqN?editors=1011（下面写的算法）

function lineerSearch() {init();var t = timer('lineerSearch benchmark');var input = this.event.target.value;for(var i = 0;i<unsortedhaystack.length - 1;i++) {if (unsortedhaystack[i] === input) {document.getElementById('result').innerHTML = 'result is... "' + unsortedhaystack[i] + '", on index: ' + i + ' of the unsorted array. Found' + ' within ' + i + ' iterations';console.log(document.getElementById('result').innerHTML);t.stop();return unsortedhaystack[i];}}}
function binarySearch () {init();sortHaystack();var t = timer('binarySearch benchmark');var firstIndex = 0;var lastIndex = haystack.length-1;var input = this.event.target.value;
//currently point in the half of the arrayvar currentIndex = (haystack.length-1)/2 | 0;var iterations = 0;
while (firstIndex <= lastIndex) {currentIndex = (firstIndex + lastIndex)/2 | 0;iterations++;if (haystack[currentIndex]  < input) {firstIndex = currentIndex + 1;//console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);} else if (haystack[currentIndex] > input) {lastIndex = currentIndex - 1;//console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);} else {document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations';console.log(document.getElementById('result').innerHTML);t.stop();return true;}}}

定义：-大O表示法是一种表示如果数据输入增加，算法性能将如何执行的表示法。

当我们谈论算法时，算法有3个重要的支柱输入、输出和处理。大O是符号表示法，它说如果数据输入以什么样的速率增加，算法处理的性能会发生变化。

我鼓励你看看这个youtube视频，它用代码示例深入解释了大O符号。

例如，假设一个算法需要5条记录，处理相同的记录所需的时间是27秒。现在，如果我们将记录增加到10，算法需要105秒。

简单地说，所花费的时间是记录数量的平方。我们可以用O（n^2）来表示。这种符号表示称为大O符号。

现在请注意，单位可以是输入中的任何东西，可以是字节、记录的位数，性能可以用任何单位来衡量，比如秒、分钟、天等。所以它不是确切的单位，而是关系。

例如，看看下面的函数“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;}}}

当我们看到任何算法的Big O符号时，我们可以将它们分为三类性能：

1. 日志和常量类别：-任何开发人员都希望看到他们在这一类别中的算法性能。
2. 线性：-开发人员不希望看到此类别中的算法，直到它是最后一个选项或唯一剩下的选项。
3. 指数：这是我们不想看到我们的算法的地方，需要返工。

因此，通过查看Big O符号，我们对算法的好区域和坏区域进行分类。

我建议您观看这个10分钟的视频，其中讨论了Big O和示例代码

https://www.youtube.com/watch?v=k6kxtzICG_g

什么是“大O”符号的简单英语解释？

我想强调“大O”符号的驱动动机是一回事，当算法的输入大小获得太大时，描述算法度量的方程的一些部分（即常数、系数、项）变成如此微不足道，我们忽略它们。忽略其部分后幸存下来的方程部分被称为算法的“大O”符号。

因此，如果输入大小不是太大，那么“大O”符号（上限）的想法就不重要了。

int sumArray (int[] nums){int sum=0;   // here we've 1 operationfor(int i=0; i < nums.length;i++){   // we've n timessum += nums[i]; // taking initialization and assignments, 3 ops}return sum;}

在上述算法中，假设您找到T(n)如下（时间复杂度）：

T(n) = 3*n + 2

要找到它的“Big O”符号，我们需要考虑非常大的输入大小：

n= 1,000,000   -> T(1,000,000) = 3,000,002n=1,000,000,000  -> T(1,000,000,000) = 3,000,000,002n=10,000,000,000  -> T(10,000,000,000) = 30,000,000,002

让我们为另一个函数F(n) = n提供类似的输入

n= 1,000,000   -> F(1,000,000) = 1,000,000n=1,000,000,000  -> F(1,000,000,000) = 1,000,000,000n=10,000,000,000  -> F(10,000,000,000) = 10,000,000,000

正如你所看到的，当输入大小得到太大时，T(n)大约等于或接近F(n)，所以常数2和系数3变得太微不足道了，现在大O"符号的想法出现了，

O(T(n)) = F(n)O(T(n)) = n

我们说T(n)的大O是n，符号是O(T(n)) = n，它是T(n)的上界，因为n得到太大。

它表示从长远来看中算法的速度。

打个字面上的比方，你不关心跑步者能以多快的速度冲刺100m短跑，甚至5k跑。你更关心马拉松运动员，最好是超级马拉松运动员（超过这个类比，你必须回到“长跑”的隐喻意义）。

你可以安全地停止阅读这里。

我添加这个答案是因为我很惊讶其余的答案是多么的数学和技术。第一句话中“长期”的概念与任意耗时的计算任务有关。与受人类能力限制的跑步不同，某些算法完成计算任务可能需要数百万年以上。

那些数学上的对数和多项式呢？事实证明，算法本质上与这些数学术语有关。如果你测量街区所有孩子的身高，你需要的时间和孩子们一样多。这本质上与n^1或n的概念有关，其中n只不过是街区上孩子的数量。在超级马拉松的情况下，你正在测量你所在城市所有孩子的身高，但你必须忽略旅行时间，并假设他们都在一条线上（否则我们会跳过当前的解释）。

假设你想把孩子们的身高按照最短身高到最长身高的顺序排列。如果只是你附近的孩子，你可能只是盯着它，然后得出有序的列表。这是“冲刺”的类比，我们真的不关心计算机科学中的冲刺，因为当你能看到一些东西时，为什么要使用计算机？

但是，如果你在你的城市，或者更好的是，你的国家，排列所有孩子的身高列表，那么你会发现你如何做到这一点本质上与数学日志和n^2联系在一起。通过你的列表找到最矮的孩子，把他的名字写在一个单独的笔记本上，然后把它从最初的笔记本上划掉，是本质上与数学n^2联系在一起。如果你想安排你的笔记本的一半，然后是另一半，然后结合结果，你会得到一个与对数联系在一起的方法。

最后，假设你首先必须去商店买卷尺。这是一个在短期冲刺中重要的努力的例子，例如测量街区上的孩子，但是当你测量城市中所有的孩子时，你可以放心地忽略这个成本。这是与低阶多项式项的数学下降的内在联系。

我希望我已经解释过，大O符号仅仅是关于长期的，数学本质上与计算方式有关，数学术语的删除和其他简化以一种相当常识的方式与长期有关。

一旦你意识到这一点，你会发现大O真的非常容易，因为所有困难的高中数学都很容易掉下来。唯一困难的部分是分析算法来识别数学术语，但是通过一些练习，你可以在分析过程中开始丢弃术语，安全地忽略算法的大块，只关注与大O相关的部分。

快乐的大O，这是我最喜欢的关于计算机科学的事情——发现一些事情比我想象的要容易得多，然后能够在谷歌面试中炫耀，当外行人被吓倒时，哈哈。

已经发布了一些很好的答案，但我想以不同的方式做出贡献。如果你想可视化正在发生的一切，你可以假设编译器可以在~1秒内执行接近10^8的操作。如果输入是在10^8中给出的，你可能想设计一个以线性方式运行的算法（比如一个未嵌套的for循环）。下面的表格可以帮助你快速搞清楚你想搞清楚的算法类型；）

当我们有一个像f(n) = n+3这样的函数，我们想知道当n接近无穷大时图的样子，我们只需删除所有常量和低阶项，因为当n变大时它们并不重要。这给我们留下了f(n) = n，所以为什么我们不能使用这个，为什么我们需要寻找一些在我们的f(n) = n+3函数之上和之下的函数，所以大O和大Omega。

因为当n接近无穷大时，说函数只是f(n) = n是不正确的，所以为了正确，我们描述了f(n) = n+3可能在的区域。我们对图的确切位置不感兴趣，因为低阶项和常数不会显著改变图的增长，所以换句话说，从上界和下界包围的区域是我们f（n）=n+3函数的模糊版本。

仅仅下降的常数和低阶项正是寻找函数的过程，这是下面和上面。

根据定义，一个函数是另一个函数的下界或上限，如果你能找到一个常量，你可以用它乘以f(n) = n函数，这样每n的输出都比原始函数大（或更小）：

f(n) = n*C > f(n) = n+3

是的，C = 2会这样做，因此我们的函数f(n) = n可以是我们的f(x) = x+3函数的上限。

下限也一样：

f(n) = n*C < f(n) = n+3

C = -2就可以了

所以f(x) = n是f(x) = x+3的上限和下限，当它的O和Omega都比它的Theta大时，这意味着它是紧密结合的。

所以大O也可能是f(x) = x^2，因为它满足条件f(n) = n^2*C > f(n) = n+3。它在我们的f(n) = n+3图之上，但是这个上界和下界之间的区域不像我们之前的边界那么精确。

从（来源）可以读到：

大O符号是一种数学符号描述了限制当参数趋向于特定的时函数的行为值或无穷大。（…）在计算机科学，大O符号用于对算法进行分类根据它们的运行时间或空间需求如何随着输入大小增长。

Big O表示法不代表每个si的函数，而是一组函数具有一定的渐近上界；正如可以从来源中读取的那样：

大O符号根据函数的增长来表征函数速率：具有相同增长率的不同函数可能是使用相同的O符号表示。

非正式地，在计算机科学时间复杂度和空间复杂度理论中，人们可以将Big O表示法视为分别具有关于时间和空间的某些最坏情况的算法的分类。例如，O(n)：

一个算法被称为线性时间/空间，或O（n）时间/空间，如果它的时间/空间复杂度是O（n）。非正式地，这意味着运行时间/空间最多与输入的大小线性增加（来源）。

O(n log n)为：

如果T（n）=O（n log^k n）某个正常数k，则称算法在拟线性时间/空间中运行；线性时间/空间是k=1（来源）的情况。

尽管如此，通常这种放松的措辞通常用于量化（在最坏的情况下）一组算法与另一组算法在输入大小增加方面的行为。要比较两类算法（e. g.、O(n log n)和O(n)），人们应该分析这两类算法在最坏的情况下随着输入大小（即， n）的增加的行为；当它趋向于无穷大时分析n

在上面的图像中，big-O表示绘制函数的渐近最小上界之一，并且不引用集合O(f(n))。

例如，在特定输入后的图像中比较O(n log n)与O(n)，O(n log n)（绿线）比O(n)（黄线）增长得更快。这就是为什么（在最坏的情况下）O(n)比O(n log n)更理想，因为可以增加输入大小，前者的增长速度比后者慢。

只是为了以快速简单的方式表达算法的复杂性。大O符号的存在是为了解释任何给定算法的最佳、最差和平均情况时间复杂度。在可能的问题实例的大小上只有数值函数。

在其他方面，精确地使用这些函数是非常困难的，因为它们倾向于：

• 有太多的颠簸-像二分搜索这样的算法通常运行对于大小正好为n=2k−1的数组（其中k是整数），因为数组分区工作得很好。这个细节不是特别但它警告我们，任何时间的时间复杂度函数算法可能非常复杂，几乎没有上下颠簸如图2.2所示。
• 需要太多的细节来精确指定-计算确切的数字在最坏的情况下执行的RAM指令需要算法指定到完整计算机程序的细节。此外，精确的答案取决于无趣的编码细节（例如，他是否使用了一个案例语句或嵌套的ifs？）。执行精确的最坏情况分析，例如T（n）=12754n2+4353 n+834lg2 n+13546显然是非常困难的工作，但提供给我们的额外信息很少比观察“时间与n二次增长”。

事实证明，在简单的上限和下限方面进行讨论要容易得多使用Big Oh符号的时间复杂度函数。Big Oh简化了我们的分析通过忽略不影响我们比较的细节水平算法。Big Oh符号忽略了乘法常量之间的差异。函数f（n）=2n和g（n）=n在Big Oh分析中是相同的

https://mimoza.marmara.edu.tr/~msakalli/cse706_12/SkienaTheAlgorithmDesignManual.pdf