Gibt es ein System hinter der Magie der Algorithmusanalyse?

Es gibt viele Fragen zur Laufzeitanalyse von Algorithmen (siehe zB Laufzeitanalyse und Algorithmusanalyse ). Viele sind ähnlich, zum Beispiel diejenigen, die nach einer Kostenanalyse von verschachtelten Schleifen oder Divide & Conquer-Algorithmen fragen, aber die meisten Antworten scheinen maßgeschneidert zu sein.

Andererseits erklären die Antworten auf eine andere allgemeine Frage das größere Bild (insbesondere in Bezug auf die asymptotische Analyse) mit einigen Beispielen, aber nicht, wie man sich die Hände schmutzig macht.

Gibt es eine strukturierte, allgemeine Methode zur Analyse der Kosten von Algorithmen? Die Kosten können die Laufzeit (Zeitkomplexität) oder ein anderes Maß für die Kosten sein, z. B. die Anzahl der ausgeführten Vergleiche, die Platzkomplexität oder etwas anderes.

^{Dies soll eine Referenzfrage werden, auf die Anfänger hinweisen können; daher sein weiter gefasster Anwendungsbereich. Bitte achten Sie darauf, allgemeine, didaktisch aufbereitete Antworten zu geben, die an mindestens einem Beispiel illustriert sind, aber dennoch viele Situationen abdecken. Vielen Dank!}

Code in Mathematik übersetzen

Bei einer (mehr oder weniger) formalen operativen Semantik können Sie den (Pseudo-) Code eines Algorithmus buchstäblich in einen mathematischen Ausdruck umwandeln, der das Ergebnis liefert, vorausgesetzt, Sie können den Ausdruck in eine nützliche Form umwandeln. Dies funktioniert gut für additive Kostenmaße wie die Anzahl der Vergleiche, Auslagerungen, Anweisungen, Speicherzugriffe, Zyklen, die einige abstrakte Maschinenanforderungen usw. erfordern.

Beispiel: Vergleiche in Bubblesort

Betrachten Sie diesen Algorithmus, der ein bestimmtes Array sortiert A:

 bubblesort(A) do                   1
  n = A.length;                     2
  for ( i = 0 to n-2 ) do           3
    for ( j = 0 to n-i-2 ) do       4
      if ( A[j] > A[j+1] ) then     5
        tmp    = A[j];              6
        A[j]   = A[j+1];            7
        A[j+1] = tmp;               8
      end                           9
    end                             10
  end                               11
end                                 12

A$n$for

$\qquad\displaystyle C_{\text{cmp}}(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \dots = \frac{n(n-1)}{2} = \binom{n}{2}$ ,

Dabei ist der Preis für jede Ausführung von Zeile 5 (die wir zählen).$1$

Beispiel: Swaps in Bubblesort

Ich werde bezeichne das Unterprogramm , das aus Linien besteht zu und durch die Kosten für die Ausführung dieses Unterprogrammes (einmal). C i , $P_{i,j}$ij$C_{i,j}$

Nehmen wir nun an, wir wollen Swaps zählen , also wie oft ausgeführt wird. Dies ist ein "Basisblock", dh ein Unterprogramm, das immer atomar ausgeführt wird und konstante Kosten verursacht (hier ). Das Zusammenziehen solcher Blöcke ist eine nützliche Vereinfachung, die wir oft anwenden, ohne darüber nachzudenken oder darüber zu sprechen.$P_{6,8}$$1$

Mit einer ähnlichen Übersetzung wie oben kommen wir zu folgender Formel:

$\qquad\displaystyle C_{\text{swaps}}(A) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$ .

$A^{(i,j)}$ bezeichnet den Zustand des Arrays vor der -ten Iteration von .$(i,j)$$P_{5,9}$

Beachten Sie, dass ich anstelle von als Parameter verwende. wir werden gleich sehen warum. Ich addiere und als Parameter von da die Kosten hier nicht davon abhängen (also im einheitlichen Kostenmodell ); im Allgemeinen könnten sie nur.$A$$n$$i$$j$$C_{5,9}$

Es ist klar, dass die Kosten von vom Inhalt von (den Werten und insbesondere) abhängen , daher müssen wir dies berücksichtigen. Jetzt stehen wir vor einer Herausforderung: Wie "packen" wir ? Nun, wir können die Abhängigkeit von explizit machen:$P_{5,9}$$A$A[j]A[j+1]$C_{5,9}$$A$

$\qquad\displaystyle C_{5,9}(A^{(i,j)}) = C_5(A^{(i,j)}) + \begin{cases} 1 &, \mathtt{A^{(i,j)}[j] > A^{(i,j)}[j+1]} \\ 0 &, \text{else} \end{cases}$ .

Für ein bestimmtes Eingabearray sind diese Kosten genau definiert, wir möchten jedoch eine allgemeinere Aussage treffen. wir müssen stärkere Annahmen treffen. Untersuchen wir drei typische Fälle.

1. Der schlimmste Fall

   wir nur die Summe betrachten und feststellen, dass , können wir eine unbedeutende Obergrenze für die Kosten finden:$C_{5,9}(A^{(i,j)}) \in \{0,1\}$

   $\qquad\displaystyle C_{\text{swaps}}(A) \leq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \frac{n(n-1)}{2} = \binom{n}{2}$ .

   Aber kann das passieren , dh wird ein für diese Obergrenze erreicht? Wie sich herausstellt, ja: Wenn wir ein umgekehrt sortiertes Array von paarweise unterschiedlichen Elementen eingeben, muss bei jeder Iteration ein Swap durchgeführt werden¹. Daher haben wir die exakte Worst-Case- Anzahl von Swaps von Bubblesort abgeleitet.$A$

2. Der beste Fall

   Umgekehrt gibt es eine triviale Untergrenze:

   $\qquad\displaystyle C_{\text{swaps}}(A) \geq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 0 = 0$ .

   Dies kann auch passieren: Auf einem bereits sortierten Array führt Bubblesort keinen einzelnen Swap aus.

3. Der durchschnittliche Fall

   Am schlimmsten und bestenfalls eine ziemliche Lücke öffnen. Aber was ist die typische Anzahl von Swaps? Um diese Frage zu beantworten, müssen wir definieren, was "typisch" bedeutet. Theoretisch haben wir keinen Grund, einen Eingang einem anderen vorzuziehen, und gehen daher normalerweise von einer gleichmäßigen Verteilung über alle möglichen Eingänge aus, dh jeder Eingang ist gleich wahrscheinlich. Wir beschränken uns auf Arrays mit paarweise unterschiedlichen Elementen und nehmen daher das zufällige Permutationsmodell an .

   Dann können wir unsere Kosten so umschreiben²:

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$

   Jetzt müssen wir über die einfache Manipulation von Summen hinausgehen. Beim Betrachten des Algorithmus stellen wir fest, dass jeder Swap genau eine Inversion in (wir tauschen immer nur die Nachbarn³). Das heißt, die Anzahl von Swaps auf ausgeführt ist genau die Anzahl von Inversionen von . Somit können wir die inneren zwei Summen ersetzen und bekommen$A$$A$$\operatorname{inv}(A)$$A$

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A)$ .

   Glücklicherweise wurde die durchschnittliche Anzahl der Inversionen ermittelt

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}$

   Welches ist unser Endergebnis. Beachten Sie, dass dies genau die Hälfte der Worst-Case-Kosten ist.

1. Beachten Sie, dass der Algorithmus sorgfältig formuliert wurde, sodass "die letzte" Iteration i = n-1der äußeren Schleife, die niemals etwas tut, nicht ausgeführt wird.
2. " " ist die mathematische Notation für "Erwartungswert", die hier nur der Durchschnitt ist.$\mathbb{E}$
3. Dabei lernen wir, dass kein Algorithmus, der nur benachbarte Elemente austauscht, asymptotisch schneller als Bubblesort sein kann (auch im Durchschnitt) - die Anzahl der Inversionen ist für alle derartigen Algorithmen eine Untergrenze. Dies gilt zB für Insertion Sort und Selection Sort .

Die allgemeine Methode

Wir haben im Beispiel gesehen, dass wir Kontrollstruktur in Mathematik übersetzen müssen; Ich werde ein typisches Ensemble von Übersetzungsregeln vorstellen. Wir haben auch gesehen, dass die Kosten für ein bestimmtes Unterprogramm vom aktuellen Status abhängen können, dh (ungefähr) von den aktuellen Werten von Variablen. Da der Algorithmus (normalerweise) den Status ändert, ist es etwas umständlich, die allgemeine Methode zu notieren. Wenn Sie sich verwirrt fühlen, schlage ich vor, dass Sie zum Beispiel zurückkehren oder sich selbst ein Bild machen.

Wir bezeichnen den aktuellen Status mit (stellen Sie sich dies als eine Reihe von Variablenzuweisungen vor). Wenn wir ein Programm auszuführen , beginnend im Zustand beenden wir im Zustand up (vorausgesetzt , endet).$\psi$P$\psi$$\psi / \mathtt{P}$P

• Einzelne Aussagen

  Bei nur einer Anweisung S;weisen Sie die Kosten . Dies ist normalerweise eine konstante Funktion.$C_S(\psi)$

• Ausdrücke

  Wenn Sie einen Ausdruck Eder Form haben E1 ∘ E2(z. B. einen arithmetischen Ausdruck, bei dem ∘es sich um Addition oder Multiplikation handeln kann), addieren Sie die Kosten rekursiv:

  $\qquad\displaystyle C_E(\psi) = c_{\circ} + C_{E_1}(\psi) + C_{E_2}(\psi)$ .

  Beachten Sie, dass

  • Die Betriebskosten möglicherweise nicht konstant, sondern hängen von den Werten von und und ab$c_{\circ}$$E_1$$E_2$
  • Die Auswertung von Ausdrücken kann den Zustand in vielen Sprachen ändern.

  Daher müssen Sie möglicherweise mit dieser Regel flexibel sein.

• Reihenfolge

  Bei einem Programm Pals Programmfolge Q;Raddieren Sie die Kosten zu

  $\qquad\displaystyle C_P(\psi) = C_Q(\psi) + C_R(\psi / \mathtt{Q})$ .

• Bedingungen

  Bei einem Programm Pder Form if A then Q else R endhängen die Kosten vom Staat ab:

  $\qquad\displaystyle C_P(\psi) = C_A(\psi) + \begin{cases} C_Q(\psi/\mathtt{A}) &, \mathtt{A} \text{ evaluates to true under } \psi \\ C_R(\psi/\mathtt{A}) &, \text{else} \end{cases}$

  In der Regel kann die Auswertung Asehr wohl den Zustand ändern, daher die Aktualisierung der Kosten für die einzelnen Filialen.

• For-Loops

  Weisen Sie bei einem vorgegebenen Programm Pdes Formulars for x = [x1, ..., xk] do Q enddie Kosten zu

  $\qquad\displaystyle C_P(\psi) = c_{\text{init_for}} + \sum_{i=1}^k c_{\text{step_for}} + C_Q(\psi_i \circ \{\mathtt{x := xi\}})$

  Dabei ist der Zustand vor der Verarbeitung für den Wert , dh nach der Iteration mit dem Setzen auf , ..., .$\psi_i$Qxixx1xi-1

  Beachten Sie die zusätzlichen Konstanten für die Schleifenwartung. Die Schleifenvariable muss erstellt ( ) und ihre Werte zugewiesen werden ( ). Dies ist relevant seit$c_{\text{init_for}}$$c_{\text{step_for}}$

  • die nächste Berechnung xikann teuer sein und
  • Eine forSchleife mit leerem Hauptteil (z. B. nach Vereinfachung in einer Best-Case-Einstellung mit bestimmten Kosten) hat keine Nullkosten, wenn sie Iterationen ausführt.

• While-Schleifen

  Weisen Sie bei einem vorgegebenen Programm Pdes Formulars while A do Q enddie Kosten zu

  $\qquad\displaystyle C_P(\psi) \\\qquad\ = C_A(\psi) + \begin{cases} 0 &, \mathtt{A} \text{ evaluates to false under } \psi \\ C_Q(\psi/\mathtt{A}) + C_P(\psi/\mathtt{A;Q}) &, \text{ else} \end{cases}$

  Durch die Überprüfung des Algorithmus kann diese Wiederholung häufig als eine ähnliche Summe wie für for-Schleifen dargestellt werden.

  Beispiel: Betrachten Sie diesen kurzen Algorithmus:

  while x > 0 do    1
    i += 1          2
    x = x/2         3
  end               4
  

  Durch die Anwendung der Regel erhalten wir

  $\qquad\displaystyle C_{1,4}(\{i := i_0; x := x_0\}) \\\qquad\ = c_< + \begin{cases} 0 &, x_0 \leq 0 \\ c_{+=} + c_/ + C_{1,4}(\{i := i_0 + 1; x := \lfloor x_0/2 \rfloor\}) &, \text{ else} \end{cases}$

  mit einigen konstanten Kosten für die einzelnen Anweisungen. Wir gehen implizit davon aus, dass diese nicht vom Zustand abhängen (die Werte von und ); Dies mag in der "Realität" zutreffen oder auch nicht: Denken Sie an Überläufe!$c_{\dots}$ix

  Jetzt müssen wir diese Wiederholung für lösen . Wir stellen fest, dass weder die Anzahl der Iterationen noch die Kosten des Schleifenkörpers vom Wert von abhängen , sodass wir ihn fallen lassen können. Wir bleiben mit dieser Wiederholung:$C_{1,4}$i

  $\qquad\displaystyle C_{1,4}(x) = \begin{cases} c_> &, x \leq 0 \\ c_> + c_{+=} + c_/ + C_{1,4}(\lfloor x/2 \rfloor) &, \text{ else} \end{cases}$

  Dies löst mit elementaren Mitteln zu

  $\qquad\displaystyle C_{1,4}(\psi) = \lceil \log_2 \psi(x) \rceil \cdot (c_> + c_{+=} + c_/) + c_>$ ,

  symbolisch den vollen Zustand wieder einführen; Wenn , dann ist .$\psi = \{ \dots, x := 5, \dots\}$$\psi(x) = 5$

• Prozeduraufrufe

  Weisen Sie bei einem Programm Pder Form M(x)für einige Parameter, bei xdenen Mes sich um eine Prozedur mit einem (benannten) Parameter phandelt, Kosten zu

  $\qquad\displaystyle C_P(\psi) = c_{\text{call}} + C_M(\psi_{\text{glob}} \circ \{p := x\})$ .

  Beachten Sie noch einmal die zusätzliche Konstante (die tatsächlich von abhängen kann !). Prozeduraufrufe sind teuer, da sie auf realen Maschinen implementiert sind und manchmal sogar die Laufzeit dominieren (z. B. naives Auswerten der Fibonacci-Nummernwiederholung).$c_{\text{call}}$$\psi$

  Ich beschreibe einige semantische Probleme, die Sie möglicherweise mit dem Staat haben. Sie möchten den globalen Status und solche lokalen Prozeduraufrufe unterscheiden. Nehmen wir an, wir übergeben hier nur den globalen Status und erhalten Meinen neuen lokalen Status, der durch Setzen des Werts auf " pto" initialisiert wird x. Darüber hinaus xkann es sich um einen Ausdruck handeln, von dem wir (normalerweise) annehmen, dass er vor dem Bestehen ausgewertet wird.

  Beispiel: Betrachten Sie die Vorgehensweise

  fac(n) do                  
    if ( n <= 1 ) do         1
      return 1               2
    else                     3
      return n * fac(n-1)    4
    end                      5
  end                        
  

  Gemäß den Regeln erhalten wir:

  $\qquad\displaystyle\begin{align*} C_{\text{fac}}(\{n := n_0\}) &= C_{1,5}(\{n := n_0\}) \\ &= c_{\leq} + \begin{cases} C_2(\{n := n_0 \}) &, n_0 \leq 1 \\ C_4(\{n := n_0 \}) &, \text{ else} \end{cases} \\ &= c_{\leq} + \begin{cases} c_{\text{return}} &, n_0 \leq 1 \\ c_{\text{return}} + c_* + c_{\text{call}} + C_{\text{fac}}(\{n := n_0 - 1\}) &, \text{ else} \end{cases} \end{align*}$

  Beachten Sie, dass wir den globalen Status außer Acht lassen, da auf fackeinen eindeutig zugegriffen wird. Diese besondere Wiederholung ist leicht zu lösen

  $\qquad\displaystyle C_{\text{fac}}(\psi) = \psi(n) \cdot (c_{\leq} + c_{\text{return}}) + (\psi(n) - 1) \cdot (c_* + c_{\text{call}})$

Wir haben die Sprachfunktionen, die Ihnen begegnen werden, in einem typischen Pseudocode behandelt. Passen Sie bei der Analyse von Pseudocodes auf hoher Ebene auf versteckte Kosten auf. im Zweifelsfall aufklappen. Die Notation mag umständlich erscheinen und ist sicherlich Geschmackssache; Die aufgeführten Konzepte können jedoch nicht ignoriert werden. Mit etwas Erfahrung können Sie jedoch sofort erkennen, welche Teile des Staates für welches Kostenmaß relevant sind, zum Beispiel "Problemgröße" oder "Anzahl der Eckpunkte". Der Rest kann fallengelassen werden - das vereinfacht die Sache erheblich!

Wenn Sie jetzt denken, dass dies viel zu kompliziert ist, seien Sie gewarnt: es ist ! Es ist eine schwierige Aufgabe, die genauen Kosten von Algorithmen in jedem Modell abzuleiten, das sich so nah an realen Maschinen befindet, dass Laufzeitvorhersagen (auch relativ) möglich sind. Dabei werden Caching und andere unangenehme Effekte auf realen Maschinen nicht berücksichtigt.

Daher wird die Algorithmusanalyse häufig so vereinfacht, dass sie mathematisch nachvollziehbar ist. Wenn Sie zum Beispiel keine genauen Kosten benötigen, können Sie zu jedem Zeitpunkt (für obere bzw. untere Grenzen) über- oder unterschätzen: Reduzieren Sie die Menge der Konstanten, beseitigen Sie die Bedingungen, vereinfachen Sie die Summen und so weiter.

Ein Hinweis zu den asymptotischen Kosten

Was Sie normalerweise in der Literatur und im Internet finden, ist die "Big-Oh-Analyse". Der eigentliche Begriff ist asymptotische Analyse. Das bedeutet, dass Sie anstelle der exakten Ableitung der Kosten wie in den Beispielen nur Kosten bis zu einem konstanten Faktor und im Grenzbereich angeben (grob gesagt "für großes ").$n$

Dies ist (oft) gerecht, da abstrakte Aussagen in der Realität einige (im Allgemeinen unbekannte) Kosten verursachen, abhängig von Maschine, Betriebssystem und anderen Faktoren, und kurze Laufzeiten möglicherweise von dem Betriebssystem dominiert werden, das den Prozess überhaupt erst einrichtet, und so weiter. Sie stören also sowieso.

Hier ist, wie die asymptotische Analyse mit diesem Ansatz zusammenhängt.

1. Identifizieren Sie dominante Vorgänge (die Kosten verursachen), dh Vorgänge, die am häufigsten auftreten (bis zu konstanten Faktoren). Im Bubblesort-Beispiel ist eine mögliche Auswahl der Vergleich in Zeile 5.

   Alternativ binden Sie alle Konstanten für Elementaroperationen an ihr Maximum (von oben) resp. ihr Minimum (von unten) und führen Sie die übliche Analyse.

2. Führen Sie die Analyse unter Verwendung der Ausführungszahlen dieser Operation als Kosten durch.
3. Lassen Sie bei der Vereinfachung Schätzungen zu. Achten Sie darauf, Schätzungen von oben nur dann zuzulassen, wenn Ihr Ziel eine Obergrenze ( ) bzw. von unten, wenn Sie untere Schranken ( ) wollen.$O$$\Omega$

Stellen Sie sicher, dass Sie die Bedeutung der Landau-Symbole verstehen . Denken Sie daran, dass solche Grenzen für alle drei Fälle existieren . Die Verwendung von impliziert keine Worst-Case-Analyse.$O$

Weitere Lektüre

In der Algorithmusanalyse gibt es noch viele weitere Herausforderungen und Tricks. Hier finden Sie einige Leseempfehlungen.

• Wie kommt man zur Laufzeit von Algorithmen?
  Wie kann man Algorithmen beschreiben, beweisen und analysieren?
• Warum Vergleiche anstelle von Laufzeit verwenden, um zwei Algorithmen zu vergleichen?
  Wie können wir annehmen, dass grundlegende Operationen mit Zahlen eine konstante Zeit benötigen?
  Was ist eine Zeiteinheit in der Laufzeitanalyse?
• Lösen oder Approximieren von Wiederholungsrelationen für Zahlenfolgen
• Grundlagen der Amortized Analysis

Es gibt viele Fragen zur Algorithmus-Analyse , die ähnliche Techniken verwenden.

Anzahl der Anweisungen zur Ausführung

Es gibt eine andere Methode, die Donald E. Knuth in seiner Reihe The Art of Computer Programming vertreten hat . Im Gegensatz zur Übersetzung des gesamten Algorithmus in eine einzige Formel funktioniert er unabhängig von der Semantik des Codes auf der Seite "Zusammensetzen" und ermöglicht es, aus der Sicht eines Adlers nur dann auf eine niedrigere Ebene zu gelangen, wenn dies erforderlich ist. Jede Aussage kann unabhängig vom Rest analysiert werden, was zu klareren Berechnungen führt. Die Technik eignet sich jedoch gut für ziemlich detaillierten Code, nicht so sehr für Pseudocode höherer Ebenen.

Die Methode

Im Prinzip ist es ganz einfach:

1. Weisen Sie jeder Anweisung einen Namen / eine Nummer zu.
2. Ordnen Sie jeder Anweisung einige Kosten .$S_i$$C_i$
3. Bestimmen Sie für jede Anweisung die Anzahl der Ausführungen .$S_i$$e_i$

4. Gesamtkosten berechnen

   $\qquad\displaystyle C = \sum_{i} e_i \cdot C_i$ .

Sie können jederzeit Schätzungen und / oder symbolische Größen einfügen, um Verallgemeinern Sie das Ergebnis entsprechend.

Beachten Sie, dass Schritt 3 beliebig komplex sein kann. In der Regel müssen Sie dort mit (asymptotischen) Schätzungen wie " " arbeiten, um Ergebnisse zu erzielen.$e_{77} \in O(n \log n)$

Beispiel: Tiefensuche

Betrachten Sie den folgenden Graph-Traversal-Algorithmus:

dfs(G, s) do
  // assert G.nodes contains s
  visited = new Array[G.nodes.size]     1
  dfs_h(G, s, visited)                  2
end 

dfs_h(G, s, visited) do
  foo(s)                                3
  visited[s] = true                     4

  v = G.neighbours(s)                   5
  while ( v != nil ) do                 6
    if ( !visited[v] ) then             7
      dfs_h(G, v, visited)              8
    end
    v = v.next                          9
  end
end

Wir nehmen an, dass der (ungerichtete) Graph durch Adjazenzlisten auf den Knoten . Sei die Anzahl der Kanten.$\{0,\dots,n-1\}$$m$

Schon beim Betrachten des Algorithmus stellen wir fest, dass einige Anweisungen genauso oft ausgeführt werden wie andere. Wir führen einige Platzhalter , und für die Ausführungszähler :$A$$B$$C$$e_i$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e_i & A & A & B & B & B & B+C & C & B-1 & C \end{array}$

Insbesondere ist da jeder rekursive Aufruf in Zeile 8 einen Aufruf in Zeile 3 verursacht (und einer durch den ursprünglichen Aufruf von ). Außerdem ist da die Bedingung einmal pro Iteration, dann aber noch einmal überprüft werden muss, um sie zu verlassen.$e_8 = e_3-1$foodfs$e_6 = e_5 + e_7$while

Es ist klar, dass . Nun würden wir bei einem Korrektheitsnachweis zeigen, dass genau einmal pro Knoten ausgeführt wird; das heißt, . Aber dann durchlaufen wir jede Adjazenzliste genau einmal und jede Kante impliziert insgesamt zwei Einträge (einen für jeden Incident-Knoten); Insgesamt erhalten wir Iterationen. Daraus leiten wir folgende Tabelle ab:$A=1$foo$B = n$$C = 2m$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e_i & 1 & 1 & n & n & n & 2m + n & 2m & n-1 & 2m \end{array}$

Dies führt uns zu Gesamtkosten von genau

$\qquad\begin{align*} C(n,m) = (C_1 + C_2 - C_8) &+\ n \cdot (C_3 + C_4 + C_5 + C_6 + C_8) \\ &+\ 2m \cdot (C_6 + C_7 + C_9) \;. \end{align*}$

Indem wir geeignete Werte für instanziieren, können wir konkretere Kosten ableiten. Wenn wir beispielsweise die Speicherzugriffe (pro Wort) zählen möchten, würden wir verwenden$C_i$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline C_i & n & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \end{array}$

und bekomme

$\qquad\displaystyle C_{\text{mem}}(n,m) = 3n + 4m$ .

Weitere Lektüre

Siehe am Ende meiner anderen Antwort .

Die Analyse von Algorithmen ist, wie das Beweisen von Theoremen, größtenteils eine Kunst (z. B. gibt es einfache Programme (wie das Collatz-Problem ), die wir nicht analysieren können). Wir können ein Algorithmuskomplexitätsproblem in ein mathematisches Problem umwandeln, wie es Raphael ausführlich beantwortet hat. Um jedoch die Kosten eines Algorithmus in Form von bekannten Funktionen auszudrücken, müssen wir Folgendes tun:

1. Verwenden Sie Techniken, die wir aus vorhandenen Analysen kennen, z. B. das Finden von Grenzen auf der Grundlage von Wiederholungen, die wir verstehen, oder von Summen / Integralen, die wir berechnen können.
2. Ändern Sie den Algorithmus in etwas, das wir analysieren können.
3. Überlegen Sie sich einen völlig neuen Ansatz.