DAA - Methodik der Analyse

Um den Ressourcenverbrauch eines Algorithmus zu messen, werden verschiedene Strategien verwendet, wie in diesem Kapitel erläutert.

Asymptotische Analyse

Das asymptotische Verhalten einer Funktion f(n) bezieht sich auf das Wachstum von f(n) wie n wird groß.

Wir ignorieren normalerweise kleine Werte von n, da wir normalerweise daran interessiert sind, abzuschätzen, wie langsam das Programm bei großen Eingaben sein wird.

Eine gute Faustregel lautet: Je langsamer die asymptotische Wachstumsrate ist, desto besser ist der Algorithmus. Obwohl es nicht immer wahr ist.

Zum Beispiel ist ein linearer Algorithmus $ f (n) = d * n + k $ immer asymptotisch besser als ein quadratischer, $ f (n) = cn ^ 2 + q $.

Lösen von Wiederholungsgleichungen

Eine Wiederholung ist eine Gleichung oder Ungleichung, die eine Funktion in Bezug auf ihren Wert bei kleineren Eingaben beschreibt. Wiederholungen werden im Allgemeinen im Divide-and-Conquer-Paradigma verwendet.

Lass uns in Erwägung ziehen T(n) die Laufzeit auf ein Größenproblem sein n.

Wenn die Problemgröße klein genug ist, sagen wir n < c wo c Ist eine Konstante, benötigt die einfache Lösung eine konstante Zeit, die als geschrieben wird θ(1). Wenn die Aufteilung des Problems eine Reihe von Unterproblemen mit der Größe $ \ frac {n} {b} $ ergibt.

Um das Problem zu lösen, ist die erforderliche Zeit a.T(n/b). Wenn wir die für die Teilung erforderliche Zeit berücksichtigen, istD(n) und die Zeit, die benötigt wird, um die Ergebnisse von Unterproblemen zu kombinieren, ist C(n)kann die Wiederholungsrelation dargestellt werden als -

$$ T (n) = \ begin {Fälle} \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \ theta (1) & if \: n \ leqslant c \\ a T (\ frac {n} {b}) + D (n) + C (n) & andernfalls \ end { Fälle} $$

Eine Wiederholungsbeziehung kann mit den folgenden Methoden gelöst werden:

Substitution Method - Bei dieser Methode erraten wir eine Grenze und beweisen mit Hilfe der mathematischen Induktion, dass unsere Annahme richtig war.
Recursion Tree Method - Bei dieser Methode wird ein Wiederholungsbaum gebildet, in dem jeder Knoten die Kosten darstellt.
Master’s Theorem - Dies ist eine weitere wichtige Technik, um die Komplexität einer Wiederholungsbeziehung zu ermitteln.

Amortisierte Analyse

Die amortisierte Analyse wird im Allgemeinen für bestimmte Algorithmen verwendet, bei denen eine Folge ähnlicher Operationen ausgeführt wird.

Die amortisierte Analyse liefert eine Begrenzung der tatsächlichen Kosten der gesamten Sequenz, anstatt die Kosten der Sequenz der Operationen separat zu begrenzen.
Die amortisierte Analyse unterscheidet sich von der Durchschnittsfallanalyse. Die Wahrscheinlichkeit ist nicht an der amortisierten Analyse beteiligt. Die amortisierte Analyse garantiert im schlimmsten Fall die durchschnittliche Leistung jeder Operation.

Es ist nicht nur ein Werkzeug zur Analyse, es ist eine Art, über das Design nachzudenken, da Design und Analyse eng miteinander verbunden sind.

Aggregatmethode

Die Aggregatmethode bietet eine globale Ansicht eines Problems. Bei dieser Methode, wennn Operationen dauern im schlimmsten Fall T(n)insgesamt. Dann sind die fortgeführten Anschaffungskosten für jede OperationT(n)/n. Obwohl unterschiedliche Vorgänge unterschiedliche Zeit in Anspruch nehmen können, werden bei diesem Verfahren unterschiedliche Kosten vernachlässigt.

Abrechnungsmethode

Bei dieser Methode werden verschiedene Vorgänge entsprechend ihren tatsächlichen Kosten unterschiedlichen Gebühren zugeordnet. Übersteigen die fortgeführten Anschaffungskosten eines Vorgangs die tatsächlichen Kosten, wird die Differenz dem Objekt als Gutschrift zugeordnet. Diese Gutschrift hilft bei der Bezahlung späterer Vorgänge, bei denen die fortgeführten Anschaffungskosten unter den tatsächlichen Kosten liegen.

Wenn die tatsächlichen Kosten und die fortgeführten Anschaffungskosten von i^th Operation sind dann $ c_ {i} $ und $ \ hat {c_ {l}} $

$$ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ hat {c_ {l}} \ geqslant \ displaystyle \ sum \ limit_ {i = 1} ^ n c_ {i} $$

Mögliche Methode

Diese Methode stellt die vorausbezahlte Arbeit als potenzielle Energie dar, anstatt vorausbezahlte Arbeit als Gutschrift zu betrachten. Diese Energie kann freigesetzt werden, um zukünftige Operationen zu finanzieren.

Wenn wir auftreten n Operationen, die mit einer anfänglichen Datenstruktur beginnen D₀. Lass uns in Erwägung ziehen,c_i als die tatsächlichen Kosten und D_i als Datenstruktur von i^thBetrieb. Die potentielle Funktion Ф ist einer reellen Zahl Ф zugeordnet (D_i), das damit verbundene Potenzial von D_i. Die fortgeführten Anschaffungskosten $ \ hat {c_ {l}} $ können definiert werden durch

$$ \ hat {c_ {l}} = c_ {i} + \ Phi (D_ {i}) - \ Phi (D_ {i-1}) $$

Somit betragen die gesamten fortgeführten Anschaffungskosten

$$ \ Anzeigestil \ Summe \ Grenzen_ {i = 1} ^ n \ hat {c_ {l}} = \ Anzeigestil \ Summe \ Grenzen_ {i = 1} ^ n (c_ {i} + \ Phi (D_ {i}) ) - \ Phi (D_ {i-1})) = \ Anzeigestil \ Summe \ Grenzen_ {i = 1} ^ n c_ {i} + \ Phi (D_ {n}) - \ Phi (D_ {0}) $ $

Dynamische Tabelle

Wenn der zugewiesene Speicherplatz für die Tabelle nicht ausreicht, müssen wir die Tabelle in eine größere Tabelle kopieren. Wenn eine große Anzahl von Elementen aus der Tabelle gelöscht wird, empfiehlt es sich, die Tabelle mit einer kleineren Größe neu zuzuweisen.

Mithilfe der amortisierten Analyse können wir zeigen, dass die amortisierten Kosten für das Einfügen und Löschen konstant sind und der nicht verwendete Speicherplatz in einer dynamischen Tabelle niemals einen konstanten Bruchteil des gesamten Speicherplatzes überschreitet.

Im nächsten Kapitel dieses Tutorials werden wir kurz auf asymptotische Notationen eingehen.