我更喜欢尽可能少的正式定义和简单的数学。
答案
快速注意，我的答案几乎可以肯定令人困惑大哦，符号（这是一个上限）带有大theta符号"θ"（这是两侧结合）。但是根据我的经验，这实际上是在非学术环境中讨论的典型代表。对造成的任何混乱表示歉意。
BigOH复杂性可以通过此图可视化：
我可以给出的最简单的定义是：
Big Oh notation is a relative representation of the complexity of an algorithm.
该句子中有一些重要且故意选择的单词：
- **relative:**您只能将苹果与苹果进行比较。您无法将算术乘法的算法与整数列表的算法进行比较。但是，进行算术操作的两种算法的比较（一个乘法，一个添加）将告诉您一些有意义的事情。
- **representation:**BigOH（以最简单的形式）减少了算法与单个变量之间的比较。该变量是根据观察结果或假设选择的。例如，通常根据比较操作（比较两个节点以确定其相对顺序）进行分类算法。假设比较很昂贵。但是，如果比较便宜，但是交换昂贵怎么办？它改变了比较；和
- **complexity:**如果我花了一秒钟才能对10,000个元素进行排序，那么我要花多长时间才能分类一百万？在这种情况下，复杂性是对其他事物的相对度量。
返回并在阅读其余内容时重新阅读上述内容。
我能想到的Bigoh最好的例子是做算术。取两个数字（123456和789012）。我们在学校学到的基本算术操作是：
- 添加;
- 减法；
- 乘法;和
- 分配。
这些都是操作或问题。一种解决这些方法称为algorithm。
加法是最简单的。您将数字（右侧）排成一列，并在列中添加数字，在结果中编写该添加的最后一个数字。该数字的" TENS"一部分被带到下一个列。
假设这些数字的添加是该算法中最昂贵的操作。有理由将这两个数字添加在一起，我们必须将6位数字添加在一起（可能携带第七位）。如果我们将两个100位数字添加在一起，则必须进行100次添加。如果我们添加two10,000位数字我们必须进行10,000次。
看到图案吗？这complexity （作为操作数量）与数字数直接成正比n 在较大的数字中。我们称之为O(n) 或者linear complexity。
减法相似（除了您可能需要借用而不是携带）。
乘法是不同的。您将数字排列在底部数字中的第一个数字，然后依次将其乘以最高数字中的每个数字，依此类推，依此类推。因此，要乘以两个6位数字，我们必须执行36个乘法。我们可能需要执行多达10或11列的添加以获得最终结果。
如果我们有两个100位数字，则需要执行10,000个乘法和200次。对于两百万个数字，我们需要做1万亿美元（10^12^）乘法和200万增加。
随着算法缩放n-平方 ， 这是O(n^2^) 或者quadratic complexity。这是介绍另一个重要概念的好时机：
We only care about the most significant portion of complexity.
精明的可能已经意识到我们可以将操作数量表示为：n^2^+ 2n。但是，正如您从我们的示例中看到的，只有两个数字一百万个数字，第二个学期（2N）变得微不足道（到该阶段到该阶段的总操作的0.0002％）。
人们可以注意到，我们在这里假设最坏的情况。在乘以6位数字的同时，如果其中一个具有4位数字，而另一个具有6位数字，则我们只有24个乘法。尽管如此，我们还是计算出" n"的最坏情况，即两者都是6位数字的情况。因此，Big Oh符号是关于算法的最坏情况。
电话簿
我能想到的下一个最好的例子是电话簿，通常称为白页或类似的电话，但随着国家而异。但是我说的是一个以姓氏，然后名称或名字的名字，可能是地址，然后是电话号码的人。
现在，如果您指示一台计算机在包含1,000,000个名称的电话簿中查找" John Smith"的电话号码，您会怎么做？忽略了您可以猜测S开始多远的事实（假设您不能），您会做什么？
典型的实现可能是开放到中间，以500,000^Th^并将其与"史密斯"进行比较。如果恰好是"史密斯，约翰"，我们真是太幸运了。更有可能的是，“约翰·史密斯"将在这个名字之前或之后。如果是在我们之后，然后将电话簿的后半部分分成两半，然后重复。如果是在此之前，我们将电话簿的前半部分分为一半，然后重复。等等。
这称为binary search无论您是否意识到，每天都在编程中每天使用。
因此，如果您想在一百万个名字的电话簿中找到一个名字，则最多可以通过使用20次来找到任何名称。在比较搜索算法时，我们认为此比较是我们的” n"。
- 对于3个名称的电话簿，它需要进行2个比较（最多）。
- 对于7，最多需要3。
- 对于15，需要4。
- …
- 对于1,000,000，需要20。
那真是太好了，不是吗？
用大术语这是O(log n) 或者logarithmic complexity 。现在，所讨论的对数可以是LN（基本E），日志~10~， 日志~2~或其他一些基础。它仍然像o一样（2n^2^）和o（100n^2^）仍然是o（n^2^）。
在这一点上，值得解释的是，BigOH可以用来用算法来确定三种情况：
- Best Case: 在电话簿搜索中，最好的情况是我们在一个比较中找到了名称。这是O(1) 或者constant complexity;
- **Expected Case:**如上所述，这是O（log n）；和
- **Worst Case:**这也是o（log n）。
通常，我们不在乎最好的情况。我们对预期和最坏的情况感兴趣。有时，其中一个或另一个会更重要。
回到电话簿。
如果您有电话号码并想找到名字怎么办？警察有一本反向电话簿，但此类查找被公众拒绝。还是他们？从技术上讲，您可以在普通电话簿中倒出一个数字。如何？
您从名字开始并比较数字。如果是一场比赛，那么很棒，如果没有，那么您继续进行下一个。您必须这样做，因为电话簿是unordered（无论如何通过电话号码）。
因此，找到给定电话号码的名称（反向查找）：
- **Best Case:**o（1）;
- **Expected Case:**o（n）（500,000）;和
- **Worst Case:**o（n）（1,000,000）。
旅行推销员
这是计算机科学中非常著名的问题，值得一提。在这个问题中，您有N城镇。每个城镇都通过一定距离的道路与1个或更多其他城镇有关。旅行推销员的问题是找到访问每个城镇的最短游览。
听起来很简单吗？再想一想。
如果您有3个城镇A，B和C，所有对之间有道路，那么您可以去：
- A → B → C
- A → C → B
- B → C → A
- B → A → C
- C → A → B
- C → B → A
嗯，实际上比这个少，因为其中一些是等效的（例如，A → B → C 和 C → B → A 是等效的，因为它们使用相同的道路，只是相反）。
实际上，有3种可能性。
- 将其带到4个城镇，您有（IIRC）12个可能性。
- 有5个是60。
- 6变为360。
这是数学操作的函数，称为factorial。基本上：
- 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,000,000
- ……
- 50！= 50×49×…×2×1 = 3.04140932×10^64^
因此，旅行推销员问题的最大问题是O(n!) 或者factorial or combinatorial complexity。
By the time you get to 200 towns there isn’t enough time left in the universe to solve the problem with traditional computers.
要考虑的东西。
多项式时间
我想快速提及的另一点是，任何复杂度为O(n^a^) 据说有polynomial complexity 或可以解决polynomial time。
O(n), O(n^2^）等都是多项式时间。在多项式时间内无法解决一些问题。因此，世界上使用某些东西。公共密钥密码学是一个很好的例子。在计算上很难找到大量的两个主要因素。如果不是这样，我们将无法使用使用的公共密钥系统。
无论如何，这就是我（希望是简单的英语）对Bigoh（修订）的解释。