Bevor ich The Art of Computer Programming (TAOCP) gelesen habe , habe ich diese Fragen nicht gründlich untersucht. Ich würde Pseudocode verwenden, um Algorithmen zu beschreiben, sie zu verstehen und die Laufzeit nur über Wachstumsordnungen zu schätzen. Das TAOCP ändert meine Meinung gründlich.
TAOCP verwendet Englisch gemischt mit Schritten und Gehe zu, um den Algorithmus zu beschreiben, und verwendet Flussdiagramme, um den Algorithmus leichter darzustellen. Es scheint auf niedrigem Niveau zu sein, aber ich finde, dass es einige Vorteile gibt, insbesondere bei Flussdiagrammen, die ich oft ignoriert habe. Wir können jeden der Pfeile mit einer Aussage über den aktuellen Stand der Dinge zum Zeitpunkt der Berechnung beschriften und einen induktiven Beweis für den Algorithmus erstellen. Der Autor sagt:
Es ist die Behauptung des Autors, dass wir wirklich verstehen, warum ein Algorithmus nur dann gültig ist, wenn wir den Punkt erreichen, an dem unser Verstand alle Behauptungen implizit ausgefüllt hat, wie dies in Abb. 4 getan wurde.
Ich habe solche Sachen nicht erlebt. Ein weiterer Vorteil ist, dass wir zählen können, wie oft jeder Schritt ausgeführt wird. Mit Kirchhoffs erstem Gesetz lässt sich das leicht überprüfen. Ich habe die Laufzeit nicht genau analysiert, sodass bei der Schätzung der Laufzeit möglicherweise weggelassen wurden.
Die Analyse von Wachstumsordnungen ist manchmal nutzlos. Beispielsweise können wir keine Quicksortierung von Heapsortierung unterscheiden, da sie alle , wobei E X die erwartete Anzahl der Zufallsvariablen X ist. Daher sollten wir die Konstante E analysieren ( T 1 ( n ) ) = A 1 n lg n + B 1 n + O ( log n )und , so können wir T 1 und T 2 besser vergleichen. Und manchmal sollten wir auch andere Größen wie Abweichungen vergleichen. Nur eine grobe Analyse der Wachstumsordnungen der Laufzeit reicht nicht aus. Wie TAOCP übersetzt die Algorithmen in Assemblersprache und berechnet die Laufzeit. Es ist zu schwer für mich, deshalb möchte ich einige Techniken kennen, um die Laufzeit etwas gröber zu analysieren, was auch für übergeordnete Sprachen wie C, C ++ nützlich ist oder Pseudocodes.
Und ich möchte wissen, welcher Beschreibungsstil hauptsächlich in Forschungsarbeiten verwendet wird und wie diese Probleme zu behandeln sind.
quelle
Antworten:
Es gibt eine Vielzahl von realisierbaren Ansätzen. Welches am besten geeignet ist, hängt davon ab
Wenn es sich bei dem Algorithmus um einen allgemein bekannten Algorithmus handelt, den Sie als Unterroutine verwenden, bleiben Sie häufig auf einer höheren Ebene. Wenn der Algorithmus das zu untersuchende Hauptobjekt ist, möchten Sie wahrscheinlich detaillierter werden. Dasselbe gilt für Analysen: Wenn Sie eine grobe Obergrenze für die Laufzeit benötigen, verfahren Sie anders, als wenn Sie eine genaue Anzahl von Anweisungen wünschen.
Ich werde Ihnen drei Beispiele für den bekannten Algorithmus Mergesort geben, die dies hoffentlich veranschaulichen.
Hohes Level
Der Algorithmus Mergesort nimmt eine Liste, teilt sie in zwei (ungefähr) gleich lange Teile auf, rekursiert auf diese Teillisten und führt die (sortierten) Ergebnisse zusammen, so dass das Endergebnis sortiert wird. Bei einzelnen oder leeren Listen wird die Eingabe zurückgegeben.
Dieser Algorithmus ist offensichtlich ein korrekter Sortieralgorithmus. Das Aufteilen und Zusammenführen der Liste kann jeweils in der Zeit implementiert werden , was eine Wiederholung für die Worst-Case-Laufzeit T ( n ) = 2 T ( n ) ergibtΘ(n) . Durch das MasterTheorem, diese auswertet bisT(n)egr& THgr;(nlogn).T(n)=2T(n2)+Θ(n) T(n)∈Θ(nlogn)
Mittleres Level
Der Algorithmus Mergesort ist durch folgenden Pseudocode gegeben:
Wir beweisen die Richtigkeit durch Induktion. Für Listen der Länge Null oder Eins ist der Algorithmus trivial korrekt. Nehmen Sie als Induktionshypothese an, dassn n>1 L n+1 L L
mergesort
bei Listen mit einer Länge von höchstens für ein willkürliches, aber festes natürliches n > 1 die Leistung korrekt ist . Nun sei L eine Liste der Länge n + 1 . Durch Induktionshypothese, und halten (nicht abnehmend) sortierte Versionen der ersten resp. zweite Hälfte von L nach den rekursiven Aufrufen. Daher wählt die Schleife in jeder Iteration das kleinste Element aus, das noch nicht untersucht wurde, und hängt es an ; somit handelt es sich um eine nicht zunehmend sortierte Liste, die alle Elemente von enthältleft
right
while
result
result
left
undright
. Die Umkehrung ist eine nicht abnehmend sortierte Version von , bei der es sich um das zurückgegebene - und gewünschte - Ergebnis handelt.Zählen wir zur Laufzeit Elementvergleiche und Listenoperationen (die die Laufzeit asymptotisch dominieren). Listen mit einer Länge von weniger als zwei verursachen keine. Für Listen mit einer Länge von haben wir die Operationen, die durch das Vorbereiten der Eingaben für die rekursiven Aufrufe verursacht werden, diejenigen aus den rekursiven Aufrufen selbst sowie die Schleife und eine . Beide rekursiven Parameter können mit jeweils höchstens n Listenoperationen berechnet werden. Die Schleife wird genau n Mal ausgeführt und jede Iteration verursacht höchstens einen Elementvergleich und genau zwei Listenoperationen. Das Finale kann implementiert werden, um 2 n zu verwendenn>1 n n 2n Listenoperationen - Jedes Element wird aus der Eingabe entfernt und in die Ausgabeliste eingefügt. Daher erfüllt die Anzahl der Vorgänge die folgende Wiederholung:
while
reverse
while
reverse
Da eindeutig nicht abnimmt, ist es ausreichend, n = 2 k für asymptotisches Wachstum zu berücksichtigen . In diesem Fall vereinfacht sich die Wiederholung zuT n=2k
Durch den Master - Satz erhalten wir , die zur Laufzeit erstreckt .T∈Θ(nlogn)
mergesort
Ultra-Low-Level
Betrachten Sie diese (verallgemeinerte) Implementierung von Mergesort in Isabelle / HOL :
Dies schließt bereits Beweise für die Richtigkeit und Kündigung ein. Finden Sie einen (fast) vollständigen Korrektheitsbeweis hier .
Für die "Laufzeit", also die Anzahl der Vergleiche, kann eine ähnliche Wiederholung wie im vorherigen Abschnitt eingerichtet werden. Anstatt den Hauptsatz zu verwenden und die Konstanten zu vergessen, können Sie ihn auch analysieren, um eine Näherung zu erhalten, die asymptotisch der wahren Größe entspricht. Die vollständige Analyse finden Sie in [1]; Hier ist eine grobe Übersicht (sie muss nicht unbedingt zum Isabelle / HOL-Code passen):
Wie oben ist die Wiederholung für die Anzahl der Vergleiche
whereen is the number of comparisons needed for merging the partial results². In order to get rid of the floors and ceils, we perform a case distinction over whether n is even:
Using nested forward/backward differences offn and en we get that
The sum matches the right-hand side of Perron's formula. We define the Dirichlet generating series ofΔ∇fk as
which together with Perron's formula leads us to
Evaluation of⊟(s) depends on which case is analysed. Other than that, we can -- after some trickery -- apply the residue theorem to get
whereA is a periodic function with values in [−1,−0.9] .
Worst case:
Average case:
quelle
Dijkstra's "A discipline of Programming" is all about analyzing and proving algorithms and designing for provability. In the preface to that book, Dijkstra explains how a very simple constructed mini-language that is properly designed to be analyzed suffices to explain many algorithms formally:
Later he explains just how small he managed to get his mini-language.
quelle