Gibt es ein System hinter der Magie der Algorithmusanalyse?

159

Es gibt viele Fragen zur Laufzeitanalyse von Algorithmen (siehe zB und ). 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!

Raphael
quelle
3
Vielen Dank an die Autoren von StackEdit , die das Schreiben so langer Posts so einfach gemacht haben , und an meine Beta-Leser FrankW , Juho , Gilles und Sebastian, die mir geholfen haben, einige Fehler zu beheben , die in früheren Entwürfen aufgetreten sind .
Raphael
1
Hey @Raphael, das ist wundervolles Zeug. Ich dachte, ich würde vorschlagen, es als PDF zusammenzustellen, um herum zu zirkulieren? So etwas könnte zu einer wirklich nützlichen Referenz werden.
Hadded
1
@hadsed: Danke, ich bin froh, dass es dir nützlich ist! Im Moment bevorzuge ich, dass ein Link zu diesem Beitrag in Umlauf gebracht wird. SE-Benutzerinhalte sind jedoch "lizenziert unter cc by-sa 3.0 mit der erforderlichen Zuweisung" (siehe Seitenfuß), sodass jeder ein PDF daraus erstellen kann, solange die Zuweisung erfolgt.
Raphael
2
Ich bin hier nicht besonders kompetent, aber ist es normal, dass in keiner Antwort auf den Hauptsatz verwiesen wird?
Babou
1
@babou Ich weiß nicht, was "normal" hier bedeutet. Aus meiner Sicht hat das Master-Theorem hier nichts zu suchen: Hier geht es um die Analyse von Algorithmen, das Master-Theorem ist ein sehr spezifisches Werkzeug zum Lösen (einiger) Wiederholungen (und das ungefähr). Da die Mathematik an anderer Stelle behandelt wurde (z. B. hier ), habe ich beschlossen, hier nur den Teil vom Algorithmus zur Mathematik abzudecken. Ich verweise in meiner Antwort auf Beiträge, die sich mit der Arbeit an der Mathematik befassen.
Raphael

Antworten:

134

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

Anfor

Ccmp(n)=i=0n2j=0ni21==n(n1)2=(n2) ,

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 , jPi,jijCi,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. 1P6,81

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

Cswaps(A)=i=0n2j=0ni2C5,9(A(i,j)) .

A(i,j) bezeichnet den Zustand des Arrays vor der -ten Iteration von .(i,j)P5,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.AnijC5,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:P5,9AA[j]A[j+1]C5,9A

C5,9(A(i,j))=C5(A(i,j))+{1,A(i,j)[j]>A(i,j)[j+1]0,else .

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:C5,9(A(i,j)){0,1}

    Cswaps(A)i=0n2j=0ni21=n(n1)2=(n2) .

    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:

    Cswaps(A)i=0n2j=0ni20=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²:

    E[Cswaps]=1n!Ai=0n2j=0ni2C5,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 bekommenAAinv(A)A

    E[Cswaps]=1n!Ainv(A) .

    Glücklicherweise wurde die durchschnittliche Anzahl der Inversionen ermittelt

    E[Cswaps]=12(n2)

    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.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).ψPψψ/PP

  • Einzelne Aussagen

    Bei nur einer Anweisung S;weisen Sie die Kosten . Dies ist normalerweise eine konstante Funktion.CS(ψ)

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

    CE(ψ)=c+CE1(ψ)+CE2(ψ) .

    Beachten Sie, dass

    • Die Betriebskosten möglicherweise nicht konstant, sondern hängen von den Werten von und und abcE1E2
    • 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

    CP(ψ)=CQ(ψ)+CR(ψ/Q) .

  • Bedingungen

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

    CP(ψ)=CA(ψ)+{CQ(ψ/A),A evaluates to true under ψCR(ψ/A),else

    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

    CP(ψ)=cinit_for+i=1kcstep_for+CQ(ψi{x:=xi})

    Dabei ist der Zustand vor der Verarbeitung für den Wert , dh nach der Iteration mit dem Setzen auf , ..., .ψiQxixx1xi-1

    Beachten Sie die zusätzlichen Konstanten für die Schleifenwartung. Die Schleifenvariable muss erstellt ( ) und ihre Werte zugewiesen werden ( ). Dies ist relevant seitcinit_forcstep_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

    CP(ψ) =CA(ψ)+{0,A evaluates to false under ψCQ(ψ/A)+CP(ψ/A;Q), else

    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

    C1,4({i:=i0;x:=x0}) =c<+{0,x00c+=+c/+C1,4({i:=i0+1;x:=x0/2}), else

    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!cix

    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:C1,4i

    C1,4(x)={c>,x0c>+c+=+c/+C1,4(x/2), else

    Dies löst mit elementaren Mitteln zu

    C1,4(ψ)=log2ψ(x)(c>+c+=+c/)+c> ,

    symbolisch den vollen Zustand wieder einführen; Wenn , dann ist .ψ={,x:=5,}ψ(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

    CP(ψ)=ccall+CM(ψglob{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).ccallψ

    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:

    Cfac({n:=n0})=C1,5({n:=n0})=c+{C2({n:=n0}),n01C4({n:=n0}), else=c+{creturn,n01creturn+c+ccall+Cfac({n:=n01}), else

    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

    Cfac(ψ)=ψ(n)(c+creturn)+(ψ(n)1)(c+ccall)

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Ω

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.

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

Raphael
quelle
1
vielleicht einige Verweise und Beispiele auf den Hauptsatz (und seine Erweiterungen ) für die asymptotische Analyse
Nikos M.
@ NikosM Es liegt hier außerhalb des Bereichs (siehe auch die Kommentare zu der Frage oben). Beachten Sie, dass ich auf unseren Referenzbeitrag über das Lösen von Wiederholungen verweise, in dem Master Theorem et al.
Raphael
@Nikos M: my $ 0.02: Während der Hauptsatz für mehrere Wiederholungen gilt, wird er für viele andere nicht gelten. Es gibt Standardmethoden zum Lösen von Wiederholungen. Und es gibt Algorithmen, für die wir nicht einmal eine Wiederholung haben, die die Laufzeit angibt. Einige fortgeschrittene Zähltechniken können erforderlich sein. Für jemanden mit einem guten mathematischen Hintergrund empfehle ich Sedgewick und Flajolets hervorragendes Buch "Analysis of Algorithms", das Kapitel wie "Wiederholungsrelationen", "Generieren von Funktionen" und "Asymptotische Approximationen" enthält. Datenstrukturen zeigen sich gelegentlich als Beispiele, und der Fokus liegt auf Methoden!
Jay
@Raphael Ich kann im Web keine Erwähnung für diese Methode "Code in Mathematik übersetzen" finden, die auf operativer Semantik basiert. Können Sie einen Verweis auf ein Buch, eine Arbeit oder einen Artikel geben, der sich formeller damit befasst? Oder haben Sie für den Fall, dass dies von Ihnen entwickelt wurde, etwas Ausführlicheres?
Wyvern666
1
@ Wyvern666 Leider nein. Ich habe es selbst erfunden, soweit jemand behaupten kann, sich so etwas auszudenken. Vielleicht schreibe ich irgendwann selbst ein zitierfähiges Werk. Das Fundament dafür ist jedoch die gesamte Arbeit rund um die analytische Kombinatorik (Flajolet, Sedgewick und viele andere). Sie beschäftigen sich die meiste Zeit nicht mit der formalen Semantik von "Code", aber sie liefern die Mathematik, um mit den additiven Kosten von "Algorithmen" im Allgemeinen umzugehen. Ich denke ehrlich, die hier vorgestellten Konzepte sind nicht sehr tiefgreifend - die Mathematik, auf die Sie sich einlassen können, ist es jedoch.
Raphael
29

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 .SiCi
  3. Bestimmen Sie für jede Anweisung die Anzahl der Ausführungen .Siei
  4. Gesamtkosten berechnen

    C=ieiCi .

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.e77O(nlogn)

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,,n1}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 :ABCei

i123456789eiAABBBB+CCB1C

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.e8=e31foodfse6=e5+e7while

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=1fooB=nC=2m

i123456789ei11nnn2m+n2mn12m

Dies führt uns zu Gesamtkosten von genau

C(n,m)=(C1+C2C8)+ n(C3+C4+C5+C6+C8)+ 2m(C6+C7+C9).

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 verwendenCi

i123456789Cin00110101

und bekomme

Cmem(n,m)=3n+4m .

Weitere Lektüre

Siehe am Ende meiner anderen Antwort .

Raphael
quelle
8

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.
Ari Trachtenberg
quelle
1
Ich schätze, ich sehe nicht, wie dies alles Nützliche und Neue hinzufügt, zusätzlich zu anderen Antworten. Die Techniken sind bereits in anderen Antworten beschrieben. Das sieht für mich eher nach einem Kommentar als nach einer Antwort auf die Frage aus.
DW
1
Ich gehe davon aus, dass die anderen Antworten beweisen, dass es keine Kunst ist. Sie sind möglicherweise nicht in der Lage, dies zu tun (z. B. Mathematik), und es ist möglicherweise etwas Kreativität (in Bezug auf die Anwendung bekannter Mathematik) erforderlich, selbst wenn Sie dies tun. Dies gilt jedoch für jede Aufgabe. Ich nehme an, wir streben hier keine neue Mathematik an. (Tatsächlich sollte diese Frage bzw. ihre Antworten den gesamten Prozess entmystifizieren.)
Raphael
4
@Raphael Ari spricht von einer erkennbaren Funktion als Bindung und nicht von der Anzahl der Anweisungen, die vom Programm ausgeführt werden (was Ihre Antwort adressiert). Der allgemeine Fall ist eine Kunst - es gibt keinen Algorithmus, der eine nichttriviale Grenze für alle Algorithmen aufstellen kann. Der übliche Fall ist jedoch eine Reihe bekannter Techniken (wie der Hauptsatz).
Gilles
@Gilles Wenn alles, wofür kein Algorithmus existiert, eine Kunst wäre, würden Handwerker (insbesondere Programmierer) schlechter bezahlt.
Raphael
1
@AriTrachlenberg macht jedoch einen wichtigen Punkt, es gibt eine Vielzahl von Möglichkeiten, die zeitliche Komplexität eines Algorithmus zu bewerten. Big-O-Notation-Definitionen selbst weisen auf ihre theoretische Natur hin oder geben sie direkt an, je nach Autor. "Worst-Case-Szenario" lässt offenbar Raum für Vermutungen und / oder neue Tatsachen unter N Personen, die im Raum diskutieren. Ganz zu schweigen von der Natur der asymptotischen Schätzungen, die etwas ... sehr Ungenaues sind.
Brian Ogden