Quick note, this is almost certainly confusing Big O notation (which is an upper bound) with Theta notation "Θ" (which is a two-side bound).
(快速说明，这几乎肯定会使Big O表示法 （上限）与Theta表示法“Θ”（两侧界线）混淆。)
In my experience, this is actually typical of discussions in non-academic settings. (以我的经验，这实际上是非学术场合中讨论的典型内容。)
Apologies for any confusion caused. (造成任何混乱，我们深表歉意。)
Big O complexity can be visualized with this graph:
(此图可以直观地显示O的复杂性：)
The simplest definition I can give for Big-O notation is this:
(我可以为Big-O表示法给出的最简单定义是：)
Big-O notation is a relative representation of the complexity of an algorithm.
(Big-O表示法是算法复杂度的相对表示。)
There are some important and deliberately chosen words in that sentence:
(该句子中有一些重要的和故意选择的单词：)
- 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.
(表示形式： Big-O（以最简单的形式）将算法之间的比较简化为单个变量。)
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?
(复杂性：如果我花一秒钟来排序10,000个元素，我要花多长时间来排序一百万个元素？)
Complexity in this instance is a relative measure to something else. (在这种情况下，复杂性是相对于其他事物的相对度量。)
Come back and reread the above when you've read the rest.
(阅读完其余内容后，请重新阅读以上内容。)
The best example of Big-O I can think of is doing arithmetic.
(我能想到的Big-O最好的例子是算术。)
Take two numbers (123456 and 789012). (取两个数字（123456和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. (该数字的“十”部分将结转到下一列。)
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). (完全有理由将这两个数字相加，我们必须将6个数字相加（可能带有7位）。)
If we add two 100 digit numbers together we have to do 100 additions. (如果我们将两个100位数相加，则必须相加100。)
If we add two 10,000 digit numbers we have to do 10,000 additions. (如果我们将两个 10,000位数字相加，则必须进行10,000次加法。)
See the pattern?
(看到图案了吗？)
The complexity (being the number of operations) is directly proportional to the number of digits n in the larger number. (复杂度 （即操作数）与较大数字中的位数n成正比。)
We call this O(n) or linear complexity . (我们称其为O（n）或线性复杂度 。)
Subtraction is similar (except you may need to borrow instead of carry).
(减法类似（除非您可能需要借用而不是进位）。)
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. (因此，要将我们的两个6位数相乘，我们必须进行36次相乘。)
We may need to do as many as 10 or 11 column adds to get the end result too. (我们可能需要做多达10个或11列合计得到最终的结果了。)
If we have two 100-digit numbers we need to do 10,000 multiplications and 200 adds.
(如果我们有两个100位数字，则需要进行10,000次乘法和200次加法。)
For two one million digit numbers we need to do one trillion (10 12 ) multiplications and two million adds. (对于两个一百万个数字，我们需要进行一万亿（10 12 ）乘法和200万加法。)
As the algorithm scales with n- squared , this is O(n 2 ) or quadratic complexity .
(随着算法按n 平方缩放，这就是O（n 2 ）或二次复杂度 。)
This is a good time to introduce another important concept: (现在是引入另一个重要概念的好时机：)
We only care about the most significant portion of complexity.
(我们只关心复杂性的最重要部分。)
The astute may have realized that we could express the number of operations as: n 2 + 2n.
(机敏的人可能已经意识到我们可以将操作数表示为：n 2 + 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). (但是，正如您从我们的示例中看到的那样，每个例子中有两个百万位数字，第二项（2n）变得微不足道（占该阶段总操作数的0.0002％）。)
One can notice that we've assumed the worst case scenario here.
(可以注意到，我们在这里假设了最坏的情况。)
While multiplying 6 digit numbers, if one of them has 4 digits and the other one has 6 digits, then we only have 24 multiplications. (在将6位数字相乘时，如果其中之一具有4位数字，而另一个具有6位数字，则我们只有24个乘法。)
Still, we calculate the worst case scenario for that 'n', ie when both are 6 digit numbers. (尽管如此，我们仍会计算该n的最坏情况，即当两者均为6位数字时。)
Hence Big-O notation is about the Worst-case scenario of an algorithm. (因此，Big-O表示法是关于算法的最坏情况。)
The Telephone Book (电话簿)
The next best example I can think of is the telephone book, normally called the White Pages or similar but it varies 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. (但是我说的是按姓氏，名字首字母或名字，可能的地址和电话号码列出的人。)
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?
(现在，如果您指示计算机在包含1,000,000个名字的电话簿中查找“ John Smith”的电话号码，您将怎么办？)
Ignoring the fact that you could guess how far in the S's started (let's assume you can't), what would you do? (忽略了一个事实，即您可以猜测S的开始距离（假设您不能），那么您会怎么做？)
A typical implementation might be to open up to the middle, take the 500,000 th and compare it to "Smith".
(一个典型的实现方式可能是打开中间位置，占据第500,000 个位置并将其与“ 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. (“ John Smith”更可能在该名称之前或之后。)
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.
(这就是所谓的二进制搜索 ，并且每天都在使用的编程你是否意识到这一点。)
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.
(因此，如果您想在一百万个电话簿中找到一个名字，则最多可以执行20次，实际上可以找到任何名字。)
In comparing search algorithms we decide that this comparison is our 'n'. (在比较搜索算法时，我们认为此比较是我们的“ n”。)
- For a phone book of 3 names it takes 2 comparisons (at most).
(对于3个名字的电话簿，最多需要进行2个比较。)
- For 7 it takes at most 3.
(对于7，最多需要3。)
- For 15 it takes 4.
(15需要4。)
- …
(…)
- For 1,000,000 it takes 20.
(1,000,000需要20。)
That is staggeringly good isn't it?
(那真是太好了，不是吗？)
In Big-O terms this is O(log n) or logarithmic complexity .
(在大澳而言，这是O（log n）的或对数的复杂性 。)
Now the logarithm in question could be ln (base e), log 10 , log 2 or some other base. (现在所讨论的对数可以是ln（底数e），log 10 ，log 2或其他一些底数。)
It doesn't matter it's still O(log n) just like O(2n 2 ) and O(100n 2 ) are still both O(n 2 ). (就像O（2n 2 ）和O（100n 2 ）都是O（n 2 ）一样，它仍然是O（log n）。)
It's worthwhile at this point to explain that Big O can be used to determine three cases with an algorithm:
(在这一点上，有必要解释一下，Big O可用于通过一种算法确定三种情况：)
Normally we don't care about the best case.
(通常情况下，我们不关心最好的情况。)<
