大澳的纯英文解释 [英] Plain English explanation of Big O

问题描述

什么是大O符号的纯英文解释？我想preFER尽可能少的正式定义，为可能的和简单的数学。

What is a plain English explanation of Big O notation? I'd prefer as little formal definition as possible and simple mathematics.

推荐答案

快速笔记，这​​几乎可以肯定是混乱大O符号（其为上界）与西塔符号（这是一个两侧方向）。在我的经验，这其实是典型的非学术环境的讨论。道歉的任何混乱造成的。

Quick note, this is almost certainly confusing Big O notation (which is an upper bound) with Theta notation (which is a two-side bound). In my experience this is actually typical of discussions in non-academic settings. Apologies for any confusion caused.

大O的复杂性可以用这个图中可以直观：

Big O complexity can be visualized with this graph:

我可以给大O符号最简单的定义是这样的：

The simplest definition I can give for Big-O notation is this:

大O符号是的一种算法的复杂度相对重presentation。

有在这句话一些重要的和故意选择的话：

There are some important and deliberately chosen words in that sentence:

  
• 相关：你只能比较苹果和苹果。你不能比较的算法来做算术乘法的算法排序整数列表。但两种算法来做算术运算（一次乘法，一次加法）进行比较会告诉你一些有意义的事;
  
• 再presentation：大澳（以最简单的形式）减少到单个变量算法之间的比较。该变量是基于观测或假设选择。例如，排序算法通常比较了基于比较操作（比较两个节点以确定它们的相对排序）。这是假定比较昂贵。但是，如果比较便宜，但交换是昂贵？它改变了比较;和
  
• 的复杂性：：如果需要我一秒钟，10,000个元素进行排序如何需要多长时间我排序百万？复杂性在这种情况下是一个相对的措施别的东西。
  

• relative: you can only compare apples to apples. You can't compare an algorithm to do arithmetic multiplication to an algorithm that sorts a list of integers. But a comparison of two algorithms to do arithmetic operations (one multiplication, one addition) will tell you something meaningful;
• representation: Big-O (in its simplest form) reduces the comparison between algorithms to a single variable. That variable is chosen based on observations or assumptions. For example, sorting algorithms are typically compared based on comparison operations (comparing two nodes to determine their relative ordering). This assumes that comparison is expensive. But what if comparison is cheap but swapping is expensive? It changes the comparison; and
• complexity: if it takes me one second to sort 10,000 elements how long will it take me to sort one million? Complexity in this instance is a relative measure to something else.

回来重读上面，当你读过的其余部分。

Come back and reread the above when you've read the rest.

的大澳我能想到的是做算术的最好例子。取两个数字（123456和789012）。我们在学校里学到基本的算术运算是：

The best example of Big-O I can think of is doing arithmetic. Take two numbers (123456 and 789012). The basic arithmetic operations we learnt in school were:

  
• 此外，
  
• 减法;
  
• 乘法;和
  
• 师。
  

• addition;
• subtraction;
• multiplication; and
• division.

每个这些是操作还是有问题。解决这些的方法被称为算法

Each of these is an operation or a problem. A method of solving these is called an algorithm.

加法是最简单的。你排队号码向上（向右侧），并在一列书面加法结果中的最后一个号码增加的数字。该号码的'几十'部分延续到下一列。

Addition is the simplest. You line the numbers up (to the right) and add the digits in a column writing the last number of that addition in the result. The 'tens' part of that number is carried over to the next column.

让我们假定加入这些号码是该算法中最昂贵的操作。按理说，要添加这两个数字加在一起，我们要加在一起6位数字（也可能携带7日）。如果再加上两个100位数在一起我们要做100增补。如果我们的两个 10,000位数字，我们要做的万补充。

Let's assume that the addition of these numbers is the most expensive operation in this algorithm. It stands to reason that to add these two numbers together we have to add together 6 digits (and possibly carry a 7th). If we add two 100 digit numbers together we have to do 100 additions. If we add two 10,000 digit numbers we have to do 10,000 additions.

请参阅模式？在复杂性（即操作的数目）成正比的较大的号码的数字的 N 的数量。我们称之为 O（N）或线性复杂

See the pattern? The complexity (being the number of operations) is directly proportional to the number of digits n in the larger number. We call this O(n) or linear complexity.

减法是相似的（除非您可能需要借入而不是进位）。

Subtraction is similar (except you may need to borrow instead of carry).

乘法是不同的。你排队号码时，采取的第一个数字，在底部号码，并通过每个数字依次乘以针对每个数字在顶部数等。因此，为了增加我们的两个6位数字，我们必须做36乘法。我们可能需要做多达10个或11列增加，以获得最终的结果了。

Multiplication is different. You line the numbers up, take the first digit in the bottom number and multiply it in turn against each digit in the top number and so on through each digit. So to multiply our two 6 digit numbers we must do 36 multiplications. We may need to do as many as 10 or 11 column adds to get the end result too.

如果我们有两个100位的数字，我们需要做的万次乘法和200补充道。两百万位数字，我们需要做的一万亿美元（10 ¹² ）乘法和200万增加了。

If we have two 100-digit numbers we need to do 10,000 multiplications and 200 adds. For two one million digit numbers we need to do one trillion (10¹²) multiplications and two million adds.

由于算法秤具有正的平方的，这是为O（n ² ）或二次复杂性 。这是一个很好的时间来介绍另外一个重要的概念：

As the algorithm scales with n-squared, this is O(n²) or quadratic complexity. This is a good time to introduce another important concept:

我们只关心复杂的最显著部分。

精明可能已经意识到，我们可以EX preSS业务的数目为：N ² + 2N。但是，当你从我们的例子中看到的有一百位每人两个数字，第二期（2N）变得不显着（占总业务的0.0002％，通过这一阶段）。

The astute may have realized that we could express the number of operations as: n² + 2n. But as you saw from our example with two numbers of a million digits apiece, the second term (2n) becomes insignificant (accounting for 0.0002% of the total operations by that stage).

可以注意到，我们假设最坏的情况下在这里。虽然乘以6位数字，如果其中有一个是4位，另一种是6位数字，那么我们只有24次乘法。然而，我们计算出最坏的情况下为N，即当两者都是6位数字。因此，大O符号是关于一个算法的最坏情况

One can notice that we've assumed the worst case scenario here. While multiplying 6 digit numbers if one of them is 4 digit and the other one is 6 digit, then we only have 24 multiplications. Still we calculate the worst case scenario for that 'n', i.e when both are 6 digit numbers. Hence Big-O notation is about the Worst-case scenario of an algorithm

我能想到的下一个最好的例子就是电话簿，通常称为白页或类似，但它会因国家而异的国家。但我说的是一个人列出按姓氏，然后缩写或第一名，可能是地址，然后电话号码。

The next best example I can think of is the telephone book, normally called the White Pages or similar but it'll vary from country to country. But I'm talking about the one that lists people by surname and then initials or first name, possibly address and then telephone numbers.

现在，如果你被指示计算机查找电话号码的电话簿，其中包含百万名约翰·史密斯，你会怎么办？忽略了一个事实，你能猜出多远，在S的开始（假设你不能），你会怎么做？

Now if you were instructing a computer to look up the phone number for "John Smith" in a telephone book that contains 1,000,000 names, what would you do? Ignoring the fact that you could guess how far in the S's started (let's assume you can't), what would you do?

一个典型的实现可能会开放到中间，拿50万^日，并把它比作史密斯夫妇。如果它正好是张三，我们刚刚得到真正的幸运。更有可能的是，约翰·史密斯将之前或名称后。如果是后我们再除以电话簿后半对半，重复动作。如果是之前，那么我们将第一电话簿一半一半，并重复。等等。

A typical implementation might be to open up to the middle, take the 500,000^th and compare it to "Smith". If it happens to be "Smith, John", we just got real lucky. Far more likely is that "John Smith" will be before or after that name. If it's after we then divide the last half of the phone book in half and repeat. If it's before then we divide the first half of the phone book in half and repeat. And so on.

这就是所谓的二进制搜索，然后你是否意识到这一点，使用的每一天的节目。

This is called a binary search and is used every day in programming whether you realize it or not.

所以，如果你想找到的百万名的电话簿名称实际上你可以找到任何名称由最多20次这样做。在比较搜索算法，我们决定这种比较是我们的'N'。

So if you want to find a name in a phone book of a million names you can actually find any name by doing this at most 20 times. In comparing search algorithms we decide that this comparison is our 'n'.

  
• 对于3名电话簿需要2比较（最多）。
  
• 对于7需要至多3。
  
• 对于15需要4。
  
• ...
  
• 1,000,000需要20。
  

• For a phone book of 3 names it takes 2 comparisons (at most).
• For 7 it takes at most 3.
• For 15 it takes 4.
• …
• For 1,000,000 it takes 20.

这是令人吃惊的好，不是吗？

That is staggeringly good isn't it?

在大澳而言，这是 O（log n）的或对数的复杂性。现在有问题的对数可能是LN（以e为底），登录 ₁₀ ，登录 ₂ 或一些其他基地。不要紧，它仍然是O（log n）的，就像O（2N ² ）和O（100N ² ）仍然既为O（n ² ）。

In Big-O terms this is O(log n) or logarithmic complexity. Now the logarithm in question could be ln (base e), log₁₀, log₂ or some other base. It doesn't matter it's still O(log n) just like O(2n²) and O(100n²) are still both O(n²).

这是值得的，在这一点上解释，大澳可以用于确定与一个算法三种情况：

It's worthwhile at this point to explain that Big O can be used to determine three cases with an algorithm:

  
• 最佳案例：在电话簿搜索，最好的情况是，我们发现在一个比较的名字。这是 O（1）或恒定的复杂性
  
• 预期的情况下：作为以上讨论，这是O（log n）的;和
  
• 最坏的情况：这也是O（log n）的
  

• Best Case: In the telephone book search, the best case is that we find the name in one comparison. This is O(1) or constant complexity;
• Expected Case: As discussed above this is O(log n); and
• Worst Case: This is also O(log n).

通常情况下，我们不关心最好的情况。我们感兴趣的预期和最坏的情况。有时一个或另一个的这些将是更重要的。

Normally we don't care about the best case. We're interested in the expected and worst case. Sometimes one or the other of these will be more important.

回到电话簿。

如果你有一个电话号码，并希望找到一个名字是什么？警方有反向电话簿但这样的查找窗口被剥夺了广大市民。或者是什么人？从技术上讲，你可以反向查找了一些在普通电话本。怎么样？

What if you have a phone number and want to find a name? The police have a reverse phone book but such look-ups are denied to the general public. Or are they? Technically you can reverse look-up a number in an ordinary phone book. How?

您启动在第一名字和比较的次数。如果它是一个比赛，伟大的，如果不是，你就移动到下一个。你必须做这种方式，因为电话簿是无序（按电话号码呢）。

You start at the first name and compare the number. If it's a match, great, if not, you move on to the next. You have to do it this way because the phone book is unordered (by phone number anyway).

因此​​，要找到一个名字给的电话号码（反向搜索）：

So to find a name given the phone number (reverse lookup):

  
• 最佳案例： O（1）;
  
• 预期的情况下： O（N）（500,000）;和
  
• 最坏的情况： O（N）（1,000,000）
  

• Best Case: O(1);
• Expected Case: O(n) (for 500,000); and
• Worst Case: O(n) (for 1,000,000).

这是在计算机科学中一个相当有名的问题，值得一提。在这个问题上，你有N个城镇。每个这些城镇的是由有一定距离的道路连接到1个或多个其它城镇。旅行商问题是要找到访问每个乡镇最短的巡回演出。

The Travelling Salesman

This is quite a famous problem in computer science and deserves a mention. In this problem you have N towns. Each of those towns is linked to 1 or more other towns by a road of a certain distance. The Travelling Salesman problem is to find the shortest tour that visits every town.

听起来很简单？再想想。

Sounds simple? Think again.

如果你有3个镇的A，B和C与所有对之间的道路，那么你可以去：

If you have 3 towns A, B and C with roads between all pairs then you could go:

  
• 在A→B→C
  
• 在A→C→早
  
• 乙→C→A
  
• B→A→C
  
• C→A→早
  
• ç→B→A
  

• A → B → C
• A → C → B
• B → C → A
• B → A → C
• C → A → B
• C → B → A

嗯，事实上有少于因为其中的一些是等价的（A→B→C和C→B→A是等价的，例如，因为它们使用相同的道路，只是反）。

Well actually there's less than that because some of these are equivalent (A → B → C and C → B → A are equivalent, for example, because they use the same roads, just in reverse).

在实际上有3个可能性。

In actuality there are 3 possibilities.

  
• 拿这4个镇，你有（IIRC）12的可能性。
  
• 随着5是60。
  
• 在6变为360。
  

• Take this to 4 towns and you have (iirc) 12 possibilities.
• With 5 it's 60.
• 6 becomes 360.

这是一个数学运算的功能叫做因子。基本上是：

This is a function of a mathematical operation called a factorial. Basically:

  
• 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×10 ⁶⁴
  

• 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 × 10⁶⁴

因此​​，大O的旅行商问题是 O（N！）或阶乘或组合的复杂性

So the Big-O of the Travelling Salesman problem is O(n!) or factorial or combinatorial complexity.

通过你得到200个乡镇出现的时候没有足够的时间留在宇宙中要解决的问题与传统的电脑。

一些思考。

还有一点我要赚快一提的是，有一个（N ^A ）是说，有多项式复杂<中的 0复杂的任何算法/ strong>或可解的多项式时间

Another point I wanted to make quick mention of is that any algorithm that has a complexity of O(n^a) is said to have polynomial complexity or is solvable in polynomial time.

为O（n），O（N ² ）等都是多项式时间。一些问题不能在多项式时间内解决。有些事情是使用，因为这样在世界上。公钥加密是一个最好的例子。它在计算上是很难找到的一个非常大的数字两个素的因素。如果不是，我们不能用我们使用的公钥系统。

O(n), O(n²) etc are all polynomial time. Some problems cannot be solved in polynomial time. Certain things are used in the world because of this. Public Key Cryptography is a prime example. It is computationally hard to find two prime factors of a very large number. If it wasn't, we couldn't use the public key systems we use.

总之，这就是它的大O的我（希望简单的英语）的说明（修订）。

Anyway, that's it for my (hopefully plain English) explanation of Big O (revised).

这篇关于大澳的纯英文解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！