Hvad er Big O Notation forklaret: Plads og tidskompleksitet

Forstår du virkelig Big O? I så fald vil dette opdatere din forståelse inden et interview. Hvis ikke, så fortvivl ikke - kom og vær med os til nogle bestræbelser inden for datalogi.

Hvis du har taget nogle algoritmerelaterede kurser, har du sikkert hørt om udtrykket Big O-notation . Hvis du ikke har gjort det, vil vi gå over det her og derefter få en dybere forståelse af, hvad det virkelig er.

Big O-notation er et af de mest grundlæggende værktøjer for computerforskere til at analysere omkostningerne ved en algoritme. Det er en god praksis for softwareingeniører også at forstå dybtgående.

Denne artikel er skrevet med den antagelse, at du allerede har tacklet noget kode. Også noget grundigt materiale kræver også grundlæggende grundlæggende matematik i gymnasiet, og det kan derfor være lidt mindre behageligt for begyndere. Men hvis du er klar, lad os komme i gang!

I denne artikel vil vi have en grundig diskussion om Big O-notation. Vi starter med et eksempel på en algoritme, der åbner vores forståelse. Derefter går vi lidt ind i matematikken for at få en formel forståelse. Derefter vil vi gennemgå nogle almindelige variationer af Big O-notation. Til sidst vil vi diskutere nogle af begrænsningerne ved Big O i et praktisk scenario. En indholdsfortegnelse kan findes nedenfor.

Indholdsfortegnelse

  1. Hvad er Big O-notation, og hvorfor betyder det noget?
  2. Formel definition af Big O-notation
  3. Big O, Little O, Omega & Theta
  4. Kompleksitetssammenligning mellem typiske store Os
  5. Tid og rumkompleksitet
  6. Bedste, gennemsnitlige, værste, forventede kompleksitet
  7. Hvorfor Big O betyder ikke noget
  8. Til sidst…

Så lad os komme i gang.

1. Hvad er Big O Notation, og hvorfor betyder det noget?

”Big O-notation er en matematisk notation, der beskriver en funktions begrænsende opførsel, når argumentet har en tendens til en bestemt værdi eller uendelighed. Det er et medlem af en familie af notationer opfundet af Paul Bachmann, Edmund Landau og andre, kollektivt kaldet Bachmann – Landau notation eller asymptotisk notation. ”- Wikipedia's definition af Big O notation

Med klare ord beskriver Big O-notationen kompleksiteten af din kode ved hjælp af algebraiske termer.

For at forstå, hvad Big O-notation er, kan vi se på et typisk eksempel, O (n²) , som normalt udtales "Big O squared" . Bogstaven "n" repræsenterer her inputstørrelsen , og funktionen "g (n) = n²" inde i "O ()" giver os en idé om, hvor kompleks algoritmen er med hensyn til inputstørrelsen.

En typisk algoritme, der har kompleksitet O (N²) ville være den udvælgelse slags algoritme. Valg slags er en sortering algoritme, der gentager gennem listen for at sikre ethvert element ved indeks jeg er den i'te mindste / største element i listen. Den CODEPEN nedenfor giver et visuelt eksempel på det.

Algoritmen kan beskrives ved hjælp af følgende kode. For at sikre, at ith- elementet er det ith mindste element på listen, gentager denne algoritme først gennem listen med en for-loop. For hvert element bruger det derefter et andet til løkke til at finde det mindste element i den resterende del af listen.

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) } }

I dette scenarie betragter vi variablen List som input, og inputstørrelse n er således antallet af elementer inde i List . Antag, at if-sætningen, og værditildelingen afgrænset af if-sætningen tager konstant tid. Derefter kan vi finde den store O-notation for SelectionSort-funktionen ved at analysere, hvor mange gange udsagnene udføres.

Først kører det indre for loop udsagnene n gange. Og så efter at jeg er inkrementeret, kører det indre for loop i n-1 gange ... ... indtil det løber en gang, så når begge for-loops deres afsluttende betingelser.

Dette ender faktisk med at give os en geometrisk sum, og med en matematik i gymnasiet ville vi finde ud af, at den indre sløjfe gentages 1 + 2… + n gange, hvilket svarer til n (n-1) / 2 gange. Hvis vi multiplicerer dette, får vi en n² / 2-n / 2.

Når vi beregner stor O-notation, bekymrer vi os kun om de dominerende termer , og vi er ligeglad med koefficienterne. Således tager vi n² som vores sidste store O. Vi skriver det som O (n²), som igen udtages som "Big O squared" .

Nu undrer du dig måske over, hvad handler dette "dominerende udtryk" om? Og hvorfor bryr vi os ikke om koefficienterne? Bare rolig, vi går over dem en efter en. Det kan være lidt svært at forstå i starten, men det giver alt sammen meget mere mening, når du læser igennem det næste afsnit.

2. Formel definition af Big O-notation

Der var engang en indisk konge, der ønskede at belønne en klog mand for sin dygtighed. Den kloge mand bad ikke om andet end hvede, der ville fylde et skakbræt.

Men her var hans regler: i den første flise vil han have 1 hvedekorn, derefter 2 på den anden flise, derefter 4 på den næste ... hver flise på skakbrættet skulle udfyldes med dobbelt så stor mængde korn som den foregående en. Den naive konge accepterede uden tøven og tænkte, at det ville være et trivielt krav at opfylde, indtil han faktisk fortsatte og prøvede det ...

Så hvor mange hvedekorn skylder kongen den kloge mand? Vi ved, at et skakbræt har 8 firkanter med 8 firkanter, som i alt udgør 64 fliser, så den sidste flise skal have 2⁶⁴ hvedekorn. Hvis du foretager en beregning online, får du 1.8446744 * 10¹⁹, dvs. ca. 18 efterfulgt af 18 nuller. Hvis vi antager, at hvert hvedekorn vejer 0,01 gram, giver det os 184.467.440.737 tons hvede. Og 184 milliarder ton er ret meget, ikke?

Tallene vokser ganske hurtigt senere for eksponentiel vækst, ikke sandt? Den samme logik gælder computeralgoritmer. Hvis den krævede indsats for at udføre en opgave vokser eksponentielt med hensyn til inputstørrelsen, kan den ende med at blive enormt stor.

Nu er firkanten på 64 4096. Hvis du føjer tallet til 2⁶⁴, går det tabt uden for de signifikante cifre. Derfor er vi kun interesserede i de dominerende vilkår, når vi ser på vækstraten. Og da vi ønsker at analysere væksten med hensyn til inputstørrelsen, indeholder koefficienterne, der kun multiplicerer antallet i stedet for at vokse med inputstørrelsen, ikke nyttig information.

Nedenfor er den formelle definition af 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.

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”.

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.

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.

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.

Spørgsmål: Et billede er repræsenteret af et 2D-array af pixels. Hvis du bruger en indlejret for løkke til at gentage hver pixel (det vil sige, du har en for-løkke, der går gennem alle kolonnerne, så en anden for løkken inde for at gå gennem alle rækkerne), hvad er algoritmens tidskompleksitet, når billede betragtes som input?

3. Big O, Little O, Omega & Theta

Big O: “f (n) er O (g (n))” iff for nogle konstanter c og N₀, f (N) ≤ cg (N) for alle N> N₀Omega: “f (n) er Ω (g ( n)) ”iff for nogle konstanter c og N₀, f (N) ≥ cg (N) for alle N> N₀Theta:“ f (n) er Θ (g (n)) ”iff f (n) er O (g (n)) og f (n) er Ω (g (n)) Lille O: “f (n) er o (g (n))” iff f (n) er O (g (n)) og f ( n) er ikke Θ (g (n)) - Formel definition af Big O, Omega, Theta og Little O

Med klare ord:

  • Big O (O()) describes the upper bound of the complexity.
  • Omega (Ω()) describes the lower bound of the complexity.
  • Theta (Θ()) describes the exact bound of the complexity.
  • Little O (o()) describes the upper bound excluding the exact bound.

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²).

Generally, when we talk about Big O, what we actually meant is Theta. It is kind of meaningless when you give an upper bound that is way larger than the scope of the analysis. This would be similar to solving inequalities by putting ∞ on the larger side, which will almost always make you right.

But how do we determine which functions are more complex than others? In the next section you will be reading, we will learn that in detail.

4. Complexity Comparison Between Typical Big Os

When we are trying to figure out the Big O for a particular function g(n), we only care about the dominant term of the function. The dominant term is the term that grows the fastest.

For example, n² grows faster than n, so if we have something like g(n) = n² + 5n + 6, it will be big O(n²). If you have taken some calculus before, this is very similar to the shortcut of finding limits for fractional polynomials, where you only care about the dominant term for numerators and denominators in the end.

But which function grows faster than the others? There are actually quite a few rules.

1. O(1) has the least complexity

Often called “constant time”, if you can create an algorithm to solve the problem in O(1), you are probably at your best. In some scenarios, the complexity may go beyond O(1), then we can analyze them by finding its O(1/g(n)) counterpart. For example, O(1/n) is more complex than O(1/n²).

2. O(log(n)) is more complex than O(1), but less complex than polynomials

As complexity is often related to divide and conquer algorithms, O(log(n)) is generally a good complexity you can reach for sorting algorithms. O(log(n)) is less complex than O(√n), because the square root function can be considered a polynomial, where the exponent is 0.5.

3. Complexity of polynomials increases as the exponent increases

For example, O(n⁵) is more complex than O(n⁴). Due to the simplicity of it, we actually went over quite many examples of polynomials in the previous sections.

4. Exponentials have greater complexity than polynomials as long as the coefficients are positive multiples of n

O(2ⁿ) is more complex than O(n⁹⁹), but O(2ⁿ) is actually less complex than O(1). We generally take 2 as base for exponentials and logarithms because things tends to be binary in Computer Science, but exponents can be changed by changing the coefficients. If not specified, the base for logarithms is assumed to be 2.

5. Factorials have greater complexity than exponentials

If you are interested in the reasoning, look up the Gamma function, it is an analytic continuation of a factorial. A short proof is that both factorials and exponentials have the same number of multiplications, but the numbers that get multiplied grow for factorials, while remaining constant for exponentials.

6. Multiplying terms

When multiplying, the complexity will be greater than the original, but no more than the equivalence of multiplying something that is more complex. For example, O(n * log(n)) is more complex than O(n) but less complex than O(n²), because O(n²) = O(n * n) and n is more complex than log(n).

To test your understanding, try ranking the following functions from the most complex to the lease complex. The solutions with detailed explanations can be found in a later section as you read. Some of them are meant to be tricky and may require some deeper understanding of math. As you get to the solution, you will understand them more.

Spørgsmål: Rangér følgende funktioner fra det mest komplekse til lejekomplekset. Løsning til afsnit 2 Spørgsmål: Det var faktisk meningen at være et trickspørgsmål for at teste din forståelse. Spørgsmålet forsøger at få dig til at svare O (n²), fordi der er en indlejret løkke. Dog formodes n at være inputstørrelsen. Da billedmatrixen er input, og hver pixel kun gentages én gang, er svaret faktisk O (n). Det næste afsnit gennemgår flere eksempler som denne.

5. Kompleksitet i tid og rum

So far, we have only been discussing the time complexity of the algorithms. That is, we only care about how much time it takes for the program to complete the task. What also matters is the space the program takes to complete the task. The space complexity is related to how much memory the program will use, and therefore is also an important factor to analyze.

The space complexity works similarly to time complexity. For example, selection sort has a space complexity of O(1), because it only stores one minimum value and its index for comparison, the maximum space used does not increase with the input size.

Some algorithms, such as bucket sort, have a space complexity of O(n), but are able to chop down the time complexity to O(1). Bucket sort sorts the array by creating a sorted list of all the possible elements in the array, then increments the count whenever the element is encountered. In the end the sorted array will be the sorted list elements repeated by their counts.

6. Best, Average, Worst, Expected Complexity

The complexity can also be analyzed as best case, worst case, average case and expected case.

Let’s take insertion sort, for example. Insertion sort iterates through all the elements in the list. If the element is larger than its previous element, it inserts the element backwards until it is larger than the previous element.

If the array is initially sorted, no swap will be made. The algorithm will just iterate through the array once, which results a time complexity of O(n). Therefore, we would say that the best-case time complexity of insertion sort is O(n). A complexity of O(n) is also often called linear complexity.

Sometimes an algorithm just has bad luck. Quick sort, for example, will have to go through the list in O(n) time if the elements are sorted in the opposite order, but on average it sorts the array in O(n * log(n)) time. Generally, when we evaluate time complexity of an algorithm, we look at their worst-case performance. More on that and quick sort will be discussed in the next section as you read.

The average case complexity describes the expected performance of the algorithm. Sometimes involves calculating the probability of each scenarios. It can get complicated to go into the details and therefore not discussed in this article. Below is a cheat-sheet on the time and space complexity of typical algorithms.

Solution to Section 4 Question:

By inspecting the functions, we should be able to immediately rank the following polynomials from most complex to lease complex with rule 3. Where the square root of n is just n to the power of 0.5.

Then by applying rules 2 and 6, we will get the following. Base 3 log can be converted to base 2 with log base conversions. Base 3 log still grows a little bit slower then base 2 logs, and therefore gets ranked after.

The rest may look a little bit tricky, but let’s try to unveil their true faces and see where we can put them.

First of all, 2 to the power of 2 to the power of n is greater than 2 to the power of n, and the +1 spices it up even more.

And then since we know 2 to the power of log(n) with based 2 is equal to n, we can convert the following. The log with 0.001 as exponent grows a little bit more than constants, but less than almost anything else.

The one with n to the power of log(log(n)) is actually a variation of the quasi-polynomial, which is greater than polynomial but less than exponential. Since log(n) grows slower than n, the complexity of it is a bit less. The one with the inverse log converges to constant, as 1/log(n) diverges to infinity.

Faktorierne kan repræsenteres ved multiplikationer og kan således konverteres til tilføjelser uden for den logaritmiske funktion. “N vælg 2” kan konverteres til et polynom med en kubikterm som den største.

Og endelig kan vi rangordne funktionerne fra de mest komplekse til de mindst komplekse.

Hvorfor BigO ikke betyder noget

!!! - ADVARSEL - !!! Indhold, der diskuteres her, accepteres generelt ikke af de fleste programmører i verden. Diskuter det på egen risiko i et interview. Folk bloggede faktisk om, hvordan de mislykkedes i deres Google-interviews, fordi de satte spørgsmålstegn ved autoriteten, som her. !!! - ADVARSEL - !!!

Since we have previously learned that the worst case time complexity for quick sort is O(n²), but O(n * log(n)) for merge sort, merge sort should be faster — right? Well you probably have guessed that the answer is false. The algorithms are just wired up in a way that makes quick sort the “quick sort”.

To demonstrate, check out this trinket.io I made. It compares the time for quick sort and merge sort. I have only managed to test it on arrays with a length up to 10000, but as you can see so far, the time for merge sort grows faster than quick sort. Despite quick sort having a worse case complexity of O(n²), the likelihood of that is really low. When it comes to the increase in speed quick sort has over merge sort bounded by the O(n * log(n)) complexity, quick sort ends up with a better performance in average.

I have also made the below graph to compare the ratio between the time they take, as it is hard to see them at lower values. And as you can see, the percentage time taken for quick sort is in a descending order.

The moral of the story is, Big O notation is only a mathematical analysis to provide a reference on the resources consumed by the algorithm. Practically, the results may be different. But it is generally a good practice trying to chop down the complexity of our algorithms, until we run into a case where we know what we are doing.

In the end…

Jeg kan godt lide at kode, lære nye ting og dele dem med samfundet. Hvis der er noget, du er særlig interesseret i, så lad mig det vide. Jeg skriver generelt om webdesign, softwarearkitektur, matematik og datalogi. Du kan finde nogle gode artikler, jeg har skrevet før, hvis du er interesseret i et af ovenstående emner.

Håber du har en god tid til at lære datalogi !!!