Was ist Big O Notation erklärt: Raum und Zeit Komplexität

Verstehst du Big O wirklich? Wenn ja, wird dies Ihr Verständnis vor einem Interview auffrischen. Wenn nicht, machen Sie sich keine Sorgen - kommen Sie zu uns, um sich in der Informatik zu engagieren.

Wenn Sie einige algorithmische Kurse besucht haben, haben Sie wahrscheinlich vom Begriff Big O-Notation gehört . Wenn nicht, werden wir hier darauf eingehen und dann ein tieferes Verständnis dafür bekommen, was es wirklich ist.

Die Big O-Notation ist eines der grundlegendsten Werkzeuge für Informatiker, um die Kosten eines Algorithmus zu analysieren. Es ist eine gute Praxis für Softwareentwickler, diese ebenfalls gründlich zu verstehen.

Dieser Artikel basiert auf der Annahme, dass Sie bereits Code in Angriff genommen haben. Einige ausführliche Materialien erfordern auch mathematische Grundlagen der High School und können daher für Anfänger etwas weniger bequem sein. Aber wenn Sie bereit sind, fangen wir an!

In diesem Artikel werden wir eine ausführliche Diskussion über die Big O-Notation führen. Wir werden mit einem Beispielalgorithmus beginnen, um unser Verständnis zu öffnen. Dann werden wir ein wenig in die Mathematik gehen, um ein formales Verständnis zu haben. Danach werden wir einige gängige Variationen der Big O-Notation durchgehen. Am Ende werden wir einige der Einschränkungen von Big O in einem praktischen Szenario diskutieren. Ein Inhaltsverzeichnis finden Sie unten.

Inhaltsverzeichnis

  1. Was ist Big O-Notation und warum ist das wichtig?
  2. Formale Definition der Big O-Notation
  3. Großes O, kleines O, Omega & Theta
  4. Komplexitätsvergleich zwischen typischen Big Os
  5. Zeit- und Raumkomplexität
  6. Beste, durchschnittliche, schlechteste, erwartete Komplexität
  7. Warum Big O keine Rolle spielt
  8. Schlussendlich…

Also lasst uns anfangen.

1. Was ist Big O Notation und warum ist das wichtig?

„Die Big O-Notation ist eine mathematische Notation, die das einschränkende Verhalten einer Funktion beschreibt, wenn das Argument zu einem bestimmten Wert oder einer bestimmten Unendlichkeit tendiert. Es gehört zu einer Familie von Notationen, die von Paul Bachmann, Edmund Landau und anderen erfunden wurden und gemeinsam als Bachmann-Landau-Notation oder asymptotische Notation bezeichnet werden. “- Wikipedia-Definition der Big O-Notation

In einfachen Worten beschreibt die Big O-Notation die Komplexität Ihres Codes mit algebraischen Begriffen.

Um zu verstehen, was Big O-Notation ist, können wir uns ein typisches Beispiel ansehen, O (n²) , das normalerweise als „Big O-Quadrat“ ausgesprochen wird . Der Buchstabe "n" repräsentiert hier die Eingabegröße , und die Funktion "g (n) = n²" innerhalb von "O ()" gibt uns eine Vorstellung davon, wie komplex der Algorithmus in Bezug auf die Eingabegröße ist.

Ein typischer Algorithmus mit der Komplexität von O (n²) wäre der Auswahlsortieralgorithmus . Die Auswahlsortierung ist ein Sortieralgorithmus, der die Liste durchläuft, um sicherzustellen, dass jedes Element am Index i das i-te kleinste / größte Element der Liste ist. Der folgende CODEPEN gibt ein visuelles Beispiel dafür.

Der Algorithmus kann durch den folgenden Code beschrieben werden. Um sicherzustellen, dass das i-te Element das i-te kleinste Element in der Liste ist, durchläuft dieser Algorithmus zuerst die Liste mit einer for-Schleife. Dann verwendet es für jedes Element eine andere for-Schleife, um das kleinste Element im verbleibenden Teil der Liste zu finden.

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 diesem Szenario betrachten wir die Variable List als Eingabe, daher ist die Eingabegröße n die Anzahl der Elemente in List . Angenommen, die if-Anweisung und die durch die if-Anweisung begrenzte Wertzuweisung benötigen eine konstante Zeit. Dann können wir die große O-Notation für die SelectionSort-Funktion finden, indem wir analysieren, wie oft die Anweisungen ausgeführt werden.

Zuerst führt die innere for-Schleife die Anweisungen innerhalb von n-mal aus. Und nachdem i inkrementiert wurde, läuft die innere for-Schleife n-1 Mal …… bis sie einmal ausgeführt wird, dann erreichen beide for-Schleifen ihre Endbedingungen.

Dies ergibt tatsächlich eine geometrische Summe, und mit etwas High-School-Mathematik würden wir feststellen, dass sich die innere Schleife 1 + 2… + n Mal wiederholt, was n (n-1) / 2 Mal entspricht. Wenn wir dies multiplizieren, erhalten wir am Ende n² / 2-n / 2.

Wenn wir die große O-Notation berechnen, kümmern wir uns nur um die dominanten Terme und nicht um die Koeffizienten. Wir nehmen also das n² als unser letztes großes O. Wir schreiben es als O (n²), was wiederum als „großes O im Quadrat“ ausgesprochen wird .

Jetzt fragen Sie sich vielleicht, worum geht es bei diesem „dominanten Begriff“ ? Und warum kümmern wir uns nicht um die Koeffizienten? Keine Sorge, wir werden sie einzeln durchgehen. Es mag am Anfang etwas schwer zu verstehen sein, aber es wird viel sinnvoller sein, wenn Sie den nächsten Abschnitt lesen.

2. Formale Definition der Big O-Notation

Es war einmal ein indischer König, der einen Weisen für seine Exzellenz belohnen wollte. Der Weise bat um nichts als etwas Weizen, der ein Schachbrett füllen würde.

Aber hier waren seine Regeln: Auf dem ersten Plättchen will er 1 Weizenkorn, dann 2 auf dem zweiten Plättchen, dann 4 auf dem nächsten… jedes Plättchen auf dem Schachbrett musste mit der doppelten Menge an Körnern gefüllt werden wie das vorherige einer. Der naive König stimmte ohne zu zögern zu und dachte, es wäre eine triviale Forderung, bis er es tatsächlich versuchte.

Wie viele Weizenkörner schuldet der König dem Weisen? Wir wissen, dass ein Schachbrett 8 mal 8 Quadrate hat, was 64 Plättchen entspricht, daher sollte das endgültige Plättchen 2⁶⁴ Weizenkörner enthalten. Wenn Sie online rechnen, erhalten Sie 1,8446744 * 10¹⁹, dh ungefähr 18, gefolgt von 18 Nullen. Unter der Annahme, dass jedes Weizenkorn 0,01 Gramm wiegt, ergibt dies 184.467.440.737 Tonnen Weizen. Und 184 Milliarden Tonnen sind ziemlich viel, nicht wahr?

Die Zahlen wachsen später ziemlich schnell für exponentielles Wachstum, nicht wahr? Die gleiche Logik gilt für Computeralgorithmen. Wenn der erforderliche Aufwand zur Erfüllung einer Aufgabe in Bezug auf die Eingabegröße exponentiell zunimmt, kann dies zu einer enormen Größe führen.

Jetzt ist das Quadrat von 64 4096. Wenn Sie diese Zahl zu 2⁶⁴ addieren, geht sie außerhalb der signifikanten Ziffern verloren. Aus diesem Grund kümmern wir uns bei der Wachstumsrate nur um die vorherrschenden Begriffe. Und da wir das Wachstum in Bezug auf die Eingabegröße analysieren möchten, enthalten die Koeffizienten, die nur die Zahl multiplizieren, anstatt mit der Eingabegröße zu wachsen, keine nützlichen Informationen.

Unten ist die formale Definition von Big O:

Die formale Definition ist nützlich, wenn Sie einen mathematischen Beweis durchführen müssen. Zum Beispiel kann die zeitliche Komplexität für die Auswahlsortierung durch die Funktion f (n) = n² / 2-n / 2 definiert werden, wie wir im vorherigen Abschnitt besprochen haben.

Wenn wir zulassen, dass unsere Funktion g (n) n² ist, können wir eine Konstante c = 1 und ein N₀ = 0 finden, und solange N> N₀ ist, ist N² immer größer als N² / 2-N / 2. Wir können dies leicht beweisen, indem wir N² / 2 von beiden Funktionen subtrahieren. Dann können wir leicht sehen, dass N² / 2> -N / 2 wahr ist, wenn N> 0. Daher können wir die Schlussfolgerung ziehen, dass f (n) = O (n²), in der anderen Auswahlsorte ist "großes O- Quadrat".

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.

Frage: Ein Bild wird durch ein 2D-Pixelarray dargestellt. Wenn Sie eine verschachtelte for-Schleife verwenden, um durch jedes Pixel zu iterieren (dh, Sie haben eine for-Schleife, die alle Spalten durchläuft, und eine andere for-Schleife, um alle Zeilen zu durchlaufen), wie hoch ist die zeitliche Komplexität des Algorithmus, wenn die Bild wird als Eingabe betrachtet?

3. Big O, Little O, Omega und Theta

Großes O: "f (n) ist O (g (n))" iff für einige Konstanten c und N₀, f (N) ≤ cg (N) für alle N> N₀Omega: "f (n) ist Ω (g () n)) ”iff für einige Konstanten c und N₀, f (N) ≥ cg (N) für alle N> N₀Theta:“ f (n) ist Θ (g (n)) ”iff f (n) ist O (g (n)) und f (n) ist Ω (g (n)) Wenig O: "f (n) ist o (g (n))", wenn f (n) O (g (n)) und f ( n) ist nicht Θ (g (n)) - Formale Definition von Big O, Omega, Theta und Little O.

In einfachen Worten:

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

Frage: Rangfolgefunktionen vom komplexesten bis zum Leasingkomplex. Lösung zu Abschnitt 2 Frage: Es sollte eigentlich eine Trickfrage sein, um Ihr Verständnis zu testen. Die Frage versucht, Sie dazu zu bringen, O (n²) zu beantworten, da eine verschachtelte for-Schleife vorhanden ist. N soll jedoch die Eingabegröße sein. Da das Bildarray die Eingabe ist und jedes Pixel nur einmal durchlaufen wurde, lautet die Antwort tatsächlich O (n). Im nächsten Abschnitt werden weitere Beispiele wie dieses behandelt.

5. Zeit- und Raumkomplexität

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.

Die Fakultäten können durch Multiplikationen dargestellt und somit in Additionen außerhalb der logarithmischen Funktion umgewandelt werden. Das "n wähle 2" kann in ein Polynom umgewandelt werden, wobei ein kubischer Term der größte ist.

Und schließlich können wir die Funktionen von den komplexesten bis zu den am wenigsten komplexen einordnen.

Warum BigO keine Rolle spielt

!!! - WARNUNG - !!! Die hier diskutierten Inhalte werden von den meisten Programmierern der Welt im Allgemeinen nicht akzeptiert . Besprechen Sie dies auf eigenes Risiko in einem Interview. Menschen gebloggt eigentlich darüber , wie sie versagt ihre Google Interviews , weil sie die Autorität in Frage gestellt, wie hier. !!! - WARNUNG - !!!

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…

I like coding, learning new things and sharing them with the community. If there is anything in which you are particularly interested, please let me know. I generally write on web design, software architecture, mathematics and data science. You can find some great articles I have written before if you are interested in any of the topics above.

Hope you have a great time learning computer science!!!