Praktische Java-Beispiele für die Big O-Notation

1. Übersicht

In diesem Tutorial werden wir darüber sprechen, was Big O Notation bedeutet. Wir werden einige Beispiele durchgehen, um die Auswirkungen auf die Laufzeit Ihres Codes zu untersuchen.

2. Die Intuition der Big O-Notation

Wir hören oft die Leistung eines Algorithmus, der mit Big O Notation beschrieben wird.

Die Untersuchung der Leistung von Algorithmen - oder der algorithmischen Komplexität - fällt in den Bereich der Algorithmusanalyse. Die Algorithmusanalyse beantwortet die Frage, wie viele Ressourcen, wie z. B. Speicherplatz oder Zeit, ein Algorithmus verbraucht.

Wir werden die Zeit als Ressource betrachten. Je weniger Zeit ein Algorithmus für die Fertigstellung benötigt, desto besser.

3. Konstante Zeitalgorithmen - O (1)

Wie wirkt sich diese Eingabegröße eines Algorithmus auf seine Laufzeit aus? Der Schlüssel zum Verständnis von Big O liegt darin, die Geschwindigkeit zu verstehen, mit der Dinge wachsen können. Die hier fragliche Rate ist die Zeit, die pro Eingabegröße benötigt wird.

Betrachten Sie diesen einfachen Code:

int n = 1000; System.out.println("Hey - your input is: " + n);

Es ist klar, dass es oben egal ist, was n ist. Die Ausführung dieses Codes dauert konstant lange. Es ist nicht abhängig von der Größe von n.

Ähnlich:

int n = 1000; System.out.println("Hey - your input is: " + n); System.out.println("Hmm.. I'm doing more stuff with: " + n); System.out.println("And more: " + n);

Das obige Beispiel ist auch eine konstante Zeit. Selbst wenn die Ausführung dreimal so lange dauert, hängt dies nicht von der Größe der Eingabe ab, n. Wir bezeichnen Konstantzeitalgorithmen wie folgt: O (1) . Beachten Sie, dass O (2) , O (3) oder sogar O (1000) dasselbe bedeuten würden.

Es ist uns egal, wie lange es dauert, nur dass es konstant dauert.

4. Logarithmische Zeitalgorithmen - O (log n)

Konstante Zeitalgorithmen sind (asymptotisch) am schnellsten. Die logarithmische Zeit ist die nächstschnellste. Leider sind sie etwas schwieriger vorstellbar.

Ein häufiges Beispiel für einen logarithmischen Zeitalgorithmus ist der binäre Suchalgorithmus. Klicken Sie hier, um zu sehen, wie Sie die binäre Suche in Java implementieren.

Wichtig ist hierbei, dass die Laufzeit proportional zum Logarithmus der Eingabe wächst (in diesem Fall log zur Basis 2):

for (int i = 1; i < n; i = i * 2){ System.out.println("Hey - I'm busy looking at: " + i); }

Wenn n 8 ist, lautet die Ausgabe wie folgt:

Hey - I'm busy looking at: 1 Hey - I'm busy looking at: 2 Hey - I'm busy looking at: 4

Unser einfacher Algorithmus hat log (8) = 3 mal ausgeführt.

5. Lineare Zeitalgorithmen - O (n)

Nach logarithmischen Zeitalgorithmen erhalten wir die nächstschnellste Klasse: lineare Zeitalgorithmen.

Wenn wir sagen, dass etwas linear wächst, meinen wir, dass es direkt proportional zur Größe seiner Eingaben wächst.

Stellen Sie sich eine einfache for-Schleife vor:

for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); }

Wie oft läuft diese for-Schleife? n mal natürlich! Wir wissen nicht genau, wie lange es dauern wird - und wir machen uns darüber keine Sorgen.

Was wir wissen ist, dass der oben vorgestellte einfache Algorithmus linear mit der Größe seiner Eingabe wächst.

Wir würden eine Laufzeit von bevorzugen 0.1n als (1000n + 1000) , aber beide sind noch lineare Algorithmen; Beide wachsen direkt proportional zur Größe ihrer Inputs.

Wieder, wenn der Algorithmus wie folgt geändert wurde:

for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); System.out.println("Hmm.. Let's have another look at: " + i); System.out.println("And another: " + i); }

Die Laufzeit wäre immer noch linear in der Größe ihrer Eingabe, n . Wir bezeichnen lineare Algorithmen wie folgt: O (n) .

Wie bei den Algorithmen für konstante Zeit kümmern wir uns nicht um die Besonderheiten der Laufzeit. O (2n + 1) ist dasselbe wie O (n) , da sich die Big O-Notation mit dem Wachstum der Eingabegrößen befasst.

6. N Log N Zeitalgorithmen - O (n log n)

n log n ist die nächste Klasse von Algorithmen. Die Laufzeit wächst proportional zu n log n der Eingabe:

for (int i = 1; i <= n; i++){ for(int j = 1; j < n; j = j * 2) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } 

Wenn beispielsweise n 8 ist, führt dieser Algorithmus 8 * log (8) = 8 * 3 = 24 Mal aus. Ob wir eine strikte Ungleichung in der for-Schleife haben oder nicht, ist für eine Big O-Notation irrelevant.

7. Polynomzeitalgorithmen - O (np)

Als nächstes haben wir polynomielle Zeitalgorithmen. Diese Algorithmen sind sogar langsamer als n log n Algorithmen.

Der Begriff Polynom ist ein allgemeiner Begriff, der quadratische (n2) , kubische (n3) , quartische (n4) usw. Funktionen enthält. Es ist wichtig zu wissen, dass O (n2) schneller ist als O (n3), was schneller ist als O (n4) usw.

Schauen wir uns ein einfaches Beispiel eines quadratischen Zeitalgorithmus an:

for (int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } 

Dieser Algorithmus wird 82 = 64 Mal ausgeführt. Wenn wir eine andere for-Schleife verschachteln würden, würde dies ein O (n3) -Algorithmus werden.

8. Exponentielle Zeitalgorithmen - O ( k n)

Jetzt betreten wir gefährliches Gebiet; Diese Algorithmen wachsen proportional zu einem Faktor, der durch die Eingabegröße potenziert wird.

Beispielsweise verdoppeln sich O (2n) -Algorithmen mit jeder zusätzlichen Eingabe. Wenn also n = 2 ist , werden diese Algorithmen viermal ausgeführt. Wenn n = 3 ist , werden sie acht Mal ausgeführt (ähnlich wie das Gegenteil von logarithmischen Zeitalgorithmen).

O(3n) algorithms triple with every additional input, O(kn) algorithms will get k times bigger with every additional input.

Let's have a look at a simple example of an O(2n) time algorithm:

for (int i = 1; i <= Math.pow(2, n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }

This algorithm will run 28 = 256 times.

9. Factorial Time Algorithms – O(n!)

In most cases, this is pretty much as bad as it'll get. This class of algorithms has a run time proportional to the factorial of the input size.

A classic example of this is solving the traveling salesman problem using a brute-force approach to solve it.

An explanation of the solution to the traveling salesman problem is beyond the scope of this article.

Instead, let's look at a simple O(n!) algorithm, as in the previous sections:

for (int i = 1; i <= factorial(n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }

where factorial(n) simply calculates n!. If n is 8, this algorithm will run 8! = 40320 times.

10. Asymptotic Functions

Big O is what is known as an asymptotic function. All this means, is that it concerns itself with the performance of an algorithm at the limit – i.e. – when lots of input is thrown at it.

Big O doesn't care about how well your algorithm does with inputs of small size. It's concerned with large inputs (think sorting a list of one million numbers vs. sorting a list of 5 numbers).

Another thing to note is that there are other asymptotic functions. Big Θ (theta) and Big Ω (omega) also both describes algorithms at the limit (remember, the limit this just means for huge inputs).

To understand the differences between these 3 important functions, we first need to know that each of Big O, Big Θ, and Big Ω describes a set (i.e., a collection of elements).

Here, the members of our sets are algorithms themselves:

  • Big O describes the set of all algorithms that run no worse than a certain speed (it's an upper bound)
  • Conversely, Big Ω describes the set of all algorithms that run no better than a certain speed (it's a lower bound)
  • Schließlich beschreibt Big Θ die Menge aller Algorithmen, die mit einer bestimmten Geschwindigkeit ausgeführt werden (es ist wie Gleichheit).

Die Definitionen, die wir oben angegeben haben, sind mathematisch nicht korrekt, aber sie helfen unserem Verständnis.

Normalerweise werden Sie Dinge hören, die mit Big O beschrieben wurden , aber es tut nicht weh, über Big Θ und Big Ω Bescheid zu wissen.

11. Schlussfolgerung

In diesem Artikel haben wir die Big O-Notation erläutert und erläutert, wie sich das Verständnis der Komplexität eines Algorithmus auf die Laufzeit Ihres Codes auswirken kann.

Eine gute Visualisierung der verschiedenen Komplexitätsklassen finden Sie hier.

Wie üblich finden Sie die Codefragmente für dieses Tutorial auf GitHub.