Komplexität eines Algorithmus

> LeekScript-Tutorial

Grund Idee

Um die Anzahl der Operationen abzuschätzen, die eine Funktion oder ein Algorithmus verbrauchen wird, ist es hilfreich, eine Vorstellung von der Beziehung zwischen der Größe der übergebenen Argumente oder der Größe eines Parameters und der maximal ausgeführten Anzahl von Operationen zu haben . Dies wird algorithmische Komplexität genannt.

Beginnen wir mit einem einfachen Beispiel: einer for-Schleife.

für (var i=0; i N gilt: f(n) < K xg(n).*

Okay, los geht's, ich habe die großen Worte herausgebracht. Was bedeutet diese Definition eigentlich? Dass die Funktion f "nicht schneller" wächst als g, wenn n zunimmt. f kann größer als g sein, aber das Verhältnis der beiden ist immer kleiner als eine bestimmte Zahl (das K der Definition). Wenden wir dies auf Code an: Nehmen wir als (mathematische) Funktion f die maximale Anzahl von Operationen, die von einem bestimmten Codestück angesichts der Größe seiner Eingabe ausgeführt werden. Wir suchen eine einfache Funktion g mit f(n)=O(g(n)). Es läuft ungefähr darauf hinaus, die größte Anzahl von Wiederholungen grundlegender Anweisungen im Code zu messen (die Kosten dieser Anweisungen werden somit unter den Teppich gekehrt: es ist das K der Definition).

Beispiele

Puh. Kommen wir zu Beispielen, wir werden klarer sehen. Kehren wir zu unserer for-Schleife von vorhin zurück:

für (var i=0; i<n; i++){ say("Ich bin eine Karotte"); }

Wenn wir f die maximale Anzahl von Operationen notieren, die von diesem Codestück ausgeführt werden, haben wir gesehen, dass f(n) ungefähr gleich 30 x n war, zuzüglich der geringen Kosten der Schleife. Tatsächlich wird die say-Anweisung n-mal wiederholt, was konstante Kosten von 30 Operationen verursacht. Wir können daher sagen, dass f von der Funktion g(n)=n dominiert wird. Somit haben wir f(n)=O(n). Wir sagen auch, dass dieses Stück Code "in O(n)" ist.

Und die Schnittfunktion von Arrays der Größe n? Wir haben gesehen, dass es ungefähr n² x (Anzahl der Push-Operationen + Kosten für den Vergleich zweier Elemente) verbraucht. Unter der Annahme, dass die Push-Kosten konstant sind (was falsch ist, aber ich möchte nicht gleich ins Detail gehen), haben wir durch Setzen von K = (Anzahl der Push-Operationen + Kosten für den Vergleich zweier Elemente ), dass die Kosten von die Schnittfunktion wird von n² dominiert: Wir sagen, dass die Schnittfunktion "in O(n²)" ist.

Somit ermöglicht die Notation O, das Wachstum der Kosten entsprechend der Größe der Eingabe zu messen: Die Schnittfunktion wird Kosten haben, die "mit der gleichen Geschwindigkeit" wie n² wachsen (wobei n die Größe der Arrays ist).

Interesse an Lauchwars

Dieser Begriff ist interessant, weil wir ein O(g(n)) oft recht einfach abschätzen können und somit wissen, ob eine Funktion sehr teuer wird, wenn der Input zunimmt. Es ist zum Beispiel uti