空间复杂度⽤什么符号表⽰_什么是⼤O符号解释：时空复杂 性
空间复杂度 ⽤什么符号表⽰
Do you really understand Big O? If so, then this will refresh your understanding before an interview. If not, don’t worry —come and join us for some endeavors in computer science.
您真的了解Big O吗？ 如果是这样，那么这将在⾯试前刷新您的理解。 如果没有，请不要担⼼-快来加⼊我们，为计算机科学做出⼀些努⼒。 If you have taken some algorithm related courses, you’ve probably heard of the term Big O notation. If you haven’t, we will go over it here, and then get a deeper understanding of what it really is.
如果您上过⼀些与算法有关的课程，您可能听说过“ Big O符号 ”⼀词。 如果您还没有，我们将在这⾥进⾏介绍，然后对它的真正含义有更深⼊的了解。 Big O notation is one of the most fundamental tools for computer scientists to analyze the cost of an algorithm. It is a good practice for software engineers to understand in-depth as well.
Big O表⽰法是计算机科学家分析算法成本的最基本⼯具之⼀。 对于软件⼯程师来说，也是⼀个深⼊了解的好习惯。
This article is written with the assumption that you have already tackled some code. Also, some in-depth material also requires high-school math fundamentals, and therefore can be a bit less comfortable to total beginners. But if you are ready, let’s get started!
本⽂假定您已经处理了⼀些代码。 另外，⼀些深⼊的材料也需要⾼中数学基础知识，因此对于初学者来说可能不太舒服。 但是，如果您准备好了，那就开始吧！
In this article, we will have an in-depth discussion about Big O notation. We will start with an example algorithm to open up our understanding. Then, we will go into the mathematics a little bit to have a formal understanding. After that we will go over some common variations of Big O notation. In the end, we will discuss some of the limitations of Big O in a practical scenario. A table of contents can be found below.
在本⽂中，我们将对Big O符号进⾏深⼊的讨论。 我们将从⼀个⽰例算法开始，以增进我们的理解。 然后，我们将对数学进⾏⼀点点正式的理解。 之后，我们将介绍Big O符号的⼀些常见变体。 最后，我们将在实际情况中讨论Big O的⼀些局限性。 ⽬录可以在下⾯到。
⽬录 (Table of Contents)
1. What is Big O notation, and why does it matter
价差预备费什么是Big O表⽰法，为什么重要
2. Formal Definition of Big O notation
⼤O符号的形式定义
3. Big O, Little O, Omega & Theta
⼤O，⼩O，Omega和Theta
4. Complexity Comparison Between Typical Big Os
典型⼤操作系统之间的复杂度⽐较
5. Time & Space Complexity
时空复杂性
6. Best, Average, Worst, Expected Complexity
最佳，平均，最差，预期复杂度
血源性疫苗7. Why Big O doesn’t matter定陵地下宫殿发掘记
为什么⼤O没关系
汇源果汁债务压顶
8. In the end…
到底…
So let’s get started.
因此，让我们开始吧。
1.什么是Big O符号，为什么重要 (1. What is Big O Notation, and why does it matter)
“Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann,
Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.”
“⼤O表⽰法是⼀种数学表⽰法，它描述了当参数趋于特定值或⽆穷⼤时函数的极限⾏为。 它是由保罗·巴赫曼(Paul Bachmann)，埃德蒙·兰道(Edmund Landau)等⼈发明的⼀系列记谱法的成员，这些记法统称为“巴赫曼·朗道记法或渐近记法”。
— Wikipedia’s definition of Big O notation
—对Big O符号的定义
In plain words, Big O notation describes the complexity of your code using algebraic terms.
简⽽⾔之，Big O表⽰法使⽤代数术语描述了代码的复杂性 。
To understand what Big O notation is, we can take a look at a typical example, O(n²), which is usually pronounced “Big O squared”. The letter “n” here represents the input size, and the function “g(n) = n²” inside the “O()” gives us an idea of how complex the algorithm is with respect to the input size.
要了解什么是Big O符号，我们可以看⼀个典型的例⼦O(n²) ，通常将其称为“ Big O squared” 。 字母“ n”代表输⼊⼤⼩ ， “
O()”内部的函数“ g(n)=n²”使我们了解算法相对于输⼊⼤⼩有多复杂。
A typical algorithm that has the complexity of O(n²) would be the selection sort algorithm. Selection sort is a sorting algorithm that iterates through the list to ensure every element at index i is the ith smallest/largest element of the list. The CODEPEN below gives a visual example of it.
具有O(n²)复杂度的典型算法是选择排序算法。 选择排序是⼀种遍历列表的排序算法，以确保索引i处的每个元素都是列表中的第i个最⼩/最⼤元素。 下⾯的CODEPEN给出了⼀个直观的⽰例。 The algorithm can be described by the following code. In order to make sure the ith element is the ith smallest element in the list, this algorithm first iterates through the list with a for loop. Then for every element it uses another for loop to find the smallest element in the remaining part of the list.
可以通过以下代码描述该算法。 为了确保第i个元素是列表中的第i个最⼩元素，此算法⾸先使⽤for循环遍历列表。 然后，对于每个元素，它使⽤另⼀个for循环在列表的其余部分中到最⼩的元素。
SelectionSort(List) {
for(i from 0 to List.Length) {
SmallestElement = List[i]
for(j from i to List.Length) {
if(SmallestElement > List[j]) {
SmallestElement = List[j]
}
}
Swap(List[i], SmallestElement)
}
}
In this scenario, we consider the variable List as the input, thus input size n is the number of element
s inside List. Assume the if statement, and the value assignment bounded by the if statement, takes constant time. Then we can find the big O notation for the SelectionSort function by analyzing how many times the statements are executed.
在这种情况下，我们将变量List视为输⼊，因此输⼊⼤⼩n是List内元素的数量 。 假设if语句以及由if语句限制的值分配花费固定时间。 然后，通过分析执⾏语句的次数，我们可以到SelectionSort函数的⼤O表⽰法。
First the inner for loop runs the statements inside n times. And then after i is incremented, the inner for loop runs for n-1 times… …until it runs once, then both of the for loops reach their terminating conditions.
⾸先，内部for循环在n次内运⾏语句。 然后，在i递增后，内部for循环运⾏n-1次……直到运⾏⼀次，然后两个for循环都达到其终⽌条件。
This actually ends up giving us a geometric sum, and with some we would find that the inner loop will repeat for 1+2 … + n times, which equals n(n-1)/2 times. If we multiply this out, we will end up getting n²/2-n/2.
实际上，这最终给了我们⼀个⼏何总和，并且通过⼀些我们会发现内部循环将重复1 + 2…+ n次，等于n(n-1)/ 2次。 如果将其相乘，最终将得到n²/ 2-n / 2。
When we calculate big O notation, we only care about the dominant terms, and we do not care about the coefficients. Thus we take the n² as our final big O. We write it as O(n²), which again is pronounced “Big O squared”.
当我们计算⼤O表⽰法时，我们只在乎优势项 ，⽽在乎系数。 因此，我们将n²作为最终的⼤O。我们将其写为O(n²)，再次称为“⼤O平⽅” 。
Now you may be wondering, what is this “dominant term” all about? And why do we not care about the coefficients? Don’t worry, we will go over them one by one. It may be a little bit hard to understand at the beginning, but it will all make a lot more sense as you read through the next section.
现在您可能想知道，这个“主导术语”到底是什么？ 为什么我们不关⼼系数呢？ 不⽤担⼼，我们将⼀⼀介绍。 ⼀开始可能很难理解，但是在阅读下⼀部分时，所有这些都将变得更加有意义。
2.⼤O符号的形式定义 (2. Formal Definition of Big O notation)
Once upon a time there was an Indian king who wanted to reward a wise man for his excellence. The wise man asked for nothing but some wheat that would fill up a chess board.
曾⼏何时，有⼀位印度国王想奖励⼀个聪明⼈，以表彰他的卓越。 聪明的⼈只要求⼀点麦⼦就可以填满棋盘。
But here were his rules: in the first tile he wants 1 grain of wheat, then 2 on the second tile, then 4 on the next one…each tile on the chess board needed to be filled by double the amount of grains as the previous one. The naïve king agreed without hesitation, thinking it would be a trivial demand to fulfill, until he actually went on and tried it…
但是这是他的规则：在第⼀个图块中，他需要1粒⼩麦，然后在第⼆个图块中需要2颗⼩麦，然后在下⼀个图块中获取4个...之⼀。 天真的国王毫不犹豫地答应了，认为满⾜他的要求是微不⾜道的，直到他继续尝试下去……
So how many grains of wheat does the king owe the wise man? We know that a chess board has 8 squares by 8 squares, which totals 64 tiles, so the final tile should have 2⁶⁴ grains of wheat. If you do a calculation online, you will end up getting 1.8446744*10¹⁹, that is about 18 followed by 18 zeroes. Assuming that each grain of wheat weights 0.01 grams, that gives us 184,467,440,737 tons of wheat.
And 184 billion tons is quite a lot, isn’t it?
那么国王⽋聪明⼈多少麦⼦呢？ 我们知道国际象棋棋盘有8平⽅乘8平⽅，总共64⽡，因此最终的⽡应该有2粒⼩麦。 如果在线进⾏计算，最终将得到1.8446744 *10¹⁹，即⼤约18，后跟18个零。 假设每粒⼩麦的重量为0.01克，那么我们就有184,467,440,737吨⼩麦。1,840亿吨是很多，不是吗？
The numbers grow quite fast later for exponential growth don’t they? The same logic goes for computer algorithms. If the required efforts to accomplish a task grow exponentially with respect to the input size, it can end up becoming enormously large.
后来数字呈指数级增长很快，不是吗？ 相同的逻辑适⽤于计算机算法。 如果完成任务所需的努⼒相对于输⼊⼤⼩呈指数增长，则最终可能变得⾮常⼤。
Now the square of 64 is 4096. If you add that number to 2⁶⁴, it will be lost outside the significant digits. This is why, when we look at the growth rate, we only care about the dominant terms. And since we want to analyze the growth with respect to the input size, the coefficients which only multiply the number rather than growing with the input size do not contain useful information.
现在64的平⽅是4096。如果将该数字加到2⁶⁴，它将在有效数字之外丢失。 这就是为什么当我们查看增长率时，我们只关⼼主导术语。
⽽且，由于我们要分析输⼊⼤⼩的增长，因此仅乘以数字⽽不是随输⼊⼤⼩增长的系数不包含有⽤的信息。
Below is the formal definition of Big O:
以下是Big O的正式定义：
The formal definition is useful when you need to perform a math proof. For example, the time complexity for selection sort can be defined by the function f(n) = n²/2-n/2 as we have discussed in the previous section.
当您需要执⾏数学证明时，形式定义很有⽤。 例如，选择排序的时间复杂度可以由函数f(n)=n²/ 2-n / 2定义，正如我们在上⼀节中讨论的那样。
If we allow our function g(n) to be n², we can find a constant c = 1, and a N₀ = 0, and so long as N > N₀, N² will always be greater than N²/2-N/2. We can easily prove this by subtracting N²/2 from both functions, then we can easily see N²/2 > -
N/2 to be true when N > 0. Therefore, we can come up with the conclusion that f(n) = O(n²), in the other selection sort is “big O squared”.
如果我们让函数g(n)为n²，我们可以到⼀个常数c = 1，⼀个N₀= 0，只要N>N₀，N²总是⼤于N²/ 2-N / 2。 我们可以通过从两个函数中减去N²/ 2来轻松证明这⼀点，然后可以很容易地看到N²/ 2> -N / 2在N> 0时为真。因此，我们可以得出以下结论：f(n)= O(n²)，在另⼀个选择中是“⼤O平⽅”。
You might have noticed a little trick here. That is, if you make g(n) grow supper fast, way faster than anything, O(g(n)) will always be great enough. For example, for any polynomial function, you can always be right by saying that they are O(2ⁿ) because 2ⁿ will eventually outgrow any polynomials.
您可能已经注意到这⾥的⼀个⼩技巧。 也就是说，如果使g(n)快速增长，⽐任何事物都快，那么O(g(n))将永远⾜够⼤。 例如，对于任何多项式函数，您总是可以正确地说它们是O(2ⁿ)，因为2ⁿ最终将超出任何多项式。
Mathematically, you are right, but generally when we talk about Big O, we want to know the tight bound of the function. You will understand this more as you read through the next section.
从数学上来说，您是对的，但是通常在我们谈论Big O时，我们想知道函数的紧密界限 。 在阅读下⼀部分时，您将更加了解这⼀点。
But before we go, let’s test your understanding with the following question. The answer will be found in later sections so it won’t be a throw away.
但是在我们开始之前，让我们⽤以下问题测试您的理解。 答案将在后⾯的章节中到，因此不会被抛弃。
Question: An image is represented by a 2D array of pixels. If you use a nested for loop to iterate through every pixel (that is, you have a for loop going through all the columns, then another for loop inside to go through all the rows), what is the time complexity of the algorithm when the image is considered as the input?
问题：图像由2D像素阵列表⽰。 如果您使⽤嵌套的for循环迭代每个像素(也就是说，有⼀个for循环遍历所有列，然后是另⼀个for循环遍历所有⾏)，那么当图像被视为输⼊？
3.⼤O，⼩O，Omega和Theta (3. Big O, Little O, Omega & Theta)
Big O: “f(n) is O(g(n))” iff for some constants c and N₀, f(N) ≤ cg(N) for all N > N₀
⼤O：对于某些常数c和N₀，“ f(n)是O(g(n))” iff，对于所有N>N₀，f(N)≤cg(N)
Omega: “f(n) is Ω(g(n))” iff for some constants c and N₀, f(N) ≥ cg(N) for all N > N₀
Ω：对于某些常数c和N₀，“ f(n)为Ω(g(n))” iff，对于所有N>N₀，f(N)≥cg(N)
Theta: “f(n) is Θ(g(n))” iff f(n) is O(g(n)) and f(n) is Ω(g(n))
Theta：“ f(n)是Θ(g(n))”，如果f(n)是O(g(n))且f(n)是Ω(g(n))
Little O: “f(n) is o(g(n))” iff f(n) is O(g(n)) and f(n) is not Θ(g(n))
⼩O：“ f(n)是o(g(n))”，如果f(n)是O(g(n))且f(n)不是Θ(g(n))
—Formal Definition of Big O, Omega, Theta and Little O
— Big O，Omega，Theta和Little O的正式定义zcom电子杂志
In plain words:
⽤简单的话说：滑精病
Big O (O()) describes the upper bound of the complexity.
⼤O(O())描述了复杂度的上限 。
Omega (Ω()) describes the lower bound of the complexity.
Ω(Ω())描述了复杂度的下限 。
Theta (Θ()) describes the exact bound of the complexity.
Theta(Θ())描述了复杂度的确切范围。
Little O (o()) describes the upper bound excluding the exact bound.
⼩O(o())描述了上限，但不包括精确界限 。
For example, the function g(n) = n² + 3n is O(n³), o(n⁴), Θ(n²) and Ω(n). But you would still be right if you say it is Ω(n²) or O(n²).
例如，函数g(n)=n²+ 3n是O(n³)，o(n⁴)，Θ(n²)和Ω(n)。 但是，如果说它是Ω(n²)或O(n²)，那您还是对的。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议