Erläutern der Relevanz der asymptotischen Komplexität von Algorithmen für die Entwurfspraxis von Algorithmen

40

In Bezug auf Algorithmen und Komplexität konzentrieren wir uns auf die asymptotische Komplexität von Algorithmen, dh die Menge an Ressourcen, die ein Algorithmus verwendet, wenn die Größe der Eingabe unendlich wird.

In der Praxis wird ein Algorithmus benötigt, der auf einer begrenzten (wenn auch möglicherweise sehr großen) Anzahl von Instanzen schnell arbeitet.

Ein in der Praxis gut funktionierender Algorithmus für die begrenzte Anzahl von Instanzen, an denen wir interessiert sind, muss keine gute asymptotische Komplexität aufweisen (eine gute Leistung für die begrenzte Anzahl von Instanzen impliziert nichts in Bezug auf die asymptotische Komplexität). In ähnlicher Weise funktioniert ein Algorithmus mit einer guten asymptotischen Komplexität in der Praxis möglicherweise nicht bei der begrenzten Anzahl von Instanzen, an denen wir interessiert sind (z. B. wegen großer Konstanten).

Warum verwenden wir asymptotische Komplexität? Wie hängen diese asymptotischen Analysen mit dem Entwurf von Algorithmen in der Praxis zusammen?

Kaveh
quelle
Eine andere relevante Frage ist: Warum ignorieren wir konstante Faktoren ?
Raphael

Antworten:

24

Die interessante Frage ist: Was ist die Alternative? Die einzige andere mir bekannte Methode ist das Testen / Benchmarking. Wir programmieren die Algorithmen, lassen sie auf dem endlichen Eingabesatz ablaufen (eine repräsentative Stichprobe davon) und vergleichen die Ergebnisse. Es gibt ein paar Probleme damit.

  • Die Ergebnisse sind maschinell nicht allgemein. Führen Sie Ihren Benchmark auf einem anderen Computer aus, und Sie erhalten mit Sicherheit, quantitativ und möglicherweise sogar qualitativ unterschiedliche Ergebnisse.
  • Die Ergebnisse sind in Bezug auf Programmiersprachen nicht allgemein. Unterschiedliche Sprachen können zu sehr unterschiedlichen Ergebnissen führen.
  • Die Ergebnisse sind in Bezug auf Implementierungsdetails nicht allgemein. Sie vergleichen buchstäblich Programme , nicht Algorithmen. Kleine Änderungen in der Implementierung können zu großen Leistungsunterschieden führen.
  • Wenn der schlimmste Fall selten ist, enthält eine zufällige Eingabestichprobe möglicherweise keine fehlerhafte Instanz. Das ist fair, wenn Sie sich mit einer durchschnittlichen Fallleistung befassen, in einigen Umgebungen jedoch Worst-Case-Garantien erforderlich sind.
  • In der Praxis ändern sich die Eingabesätze. In der Regel werden die Eingaben mit der Zeit größer. Wenn Sie Ihren Benchmark nicht alle sechs Monate wiederholen (ja, einige Daten wachsen so schnell), sind Ihre Ergebnisse bald wertlos¹.

Das heißt, das Ignorieren aller Arten von Effekten und Konstanten in der Analyse ist typisch, kann aber (in Bezug auf die Praxis) als faul bezeichnet werden. Es dient dazu , algorithmische Ideen mehr zu vergleichen als die Leistung einer gegebenen (sogar Pseudocode-) Implementierung zu bestimmen. Der Gemeinde ist bekannt, dass dies grob ist und dass häufig eine nähere Betrachtung erforderlich ist. Beispielsweise ist Quicksort für (sehr) kleine Eingaben weniger effizient als die Einfügesortierung. Um fair zu sein, ist eine genauere Analyse in der Regel schwierig² .

Eine andere, nachträgliche Rechtfertigung für den formalen, abstrakten Standpunkt ist, dass die Dinge auf dieser Ebene oft klarer sind. Jahrzehntelange theoretische Studien haben daher eine Vielzahl von algorithmischen Ideen und Datenstrukturen hervorgebracht, die in der Praxis von Nutzen sind. Der theoretisch optimale Algorithmus ist nicht immer derjenige, den Sie in der Praxis verwenden möchten - es gibt andere Überlegungen als die Leistung. denke, Fibonacci Haufen - und dieses Label kann nicht einmal einzigartig sein. Für einen typischen Programmierer, der sich mit der Optimierung von arithmetischen Ausdrücken befasst, ist es schwierig, auf dieser Ebene eine neue Idee zu finden (nicht zu sagen, dass dies nicht der Fall ist). Sie kann (und sollte) diese Optimierungen an der assimilierten Idee vornehmen.

Es gibt formale, theoretische Instrumente, um die Lücke zum Praktizieren zu schließen. Beispiele sind

  • Berücksichtigung der Speicherhierarchie (und anderer E / A),
  • Analyse des Durchschnittsfalls (falls zutreffend),
  • Analysieren der Anzahl einzelner Aussagen (anstelle von abstrakten Kostenmaßen) und
  • konstante Faktoren bestimmen.

Beispielsweise ist Knuth dafür bekannt, die Anzahl verschiedener Anweisungen (für eine bestimmte Implementierung in einem bestimmten Modell) buchstäblich zu zählen, um einen präzisen Vergleich von Algorithmen zu ermöglichen. Dieser Ansatz ist auf abstrakter Ebene unmöglich und in komplexeren Modellen (denken Sie an Java) schwer umzusetzen. Siehe [4] für ein modernes Beispiel.

Es wird immer eine Lücke zwischen Theorie und Praxis geben. Wir arbeiten derzeit an einem Tool³ mit dem Ziel, das Beste aus beiden Welten zu kombinieren, um fundierte Vorhersagen sowohl für die algorithmischen Kosten als auch für die Laufzeit (im Durchschnitt) zu treffen. Bisher konnten wir jedoch keine Szenarien beseitigen, in denen ein Algorithmus höher ist kostet aber eine geringere Laufzeit (auf einigen Rechnern) als eine gleichwertige (obwohl wir das erkennen können und die Suche nach dem Grund unterstützen).

Ich empfehle den Praktikern, die Theorie zu verwenden, um den Raum der Algorithmen zu filtern, bevor Benchmarks ausgeführt werden:

if ( input size forever bounded? ) {
  benchmark available implementations, choose best
  schedule new benchmarks for when machine changes
}
else {
  benchmark implementations of all asymptotically good algorithms
  choose the best
  schedule new benchmarks for when machine changes or inputs grow significantly
}

  1. Es kann verrückte Änderungen in der absoluten und relativen Leistung geben, wenn die Anzahl der Cache-Fehlschläge zunimmt, was normalerweise der Fall ist, wenn die Eingaben zunehmen, die Maschine jedoch gleich bleibt.
  2. Nach wie vor sind führende Forscher auf diesem Gebiet nicht in der Lage, dies zu tun.
  3. Finden Sie das Werkzeug hier . Eine Beispielanwendung wurde in Engineering Java 7s Dual Pivot Quicksort Using MaLiJAn von S. Wild et al. (2012) [ Vorabdruck ]
  4. Durchschnittliche Fallanalyse von Java 7's Dual Pivot Quicksort von S. Wild und M. Nebel (2012) - [ Preprint ]
Raphael
quelle
3
Das reine Studium der Algorithmentheorie wird Ihr Auge schärfen und Ihr Abstraktionsgehirn auf Algorithmen trainieren, was Ihnen ein weiteres Werkzeug für die Bewertung von Code in der täglichen Programmierung bietet. Entfernen Sie sich vom Code, bewerten Sie das Prinzip, verbessern Sie es und übersetzen Sie es zurück in den Code. Beispiel: "Ah, ich verstehe, Sie möchten ein Wörterbuch programmieren. Aber Sie programmieren im Wesentlichen Listen. Warum versuchen Sie es nicht mit Bäumen?"
Raphael
Die Grenzen der asymptotischen Analyse werden offensichtlich, wenn Sie tiefer graben. Quicksort ist ein prominentes Beispiel .
Raphael
1
FWIW, ich habe eine neuere Schnappschuss meiner Meinungen zu Landau - Notation geschrieben hier .
Raphael
11

Ich gehe davon aus, dass sich diese Frage aus dem Unterrichten eines Kurses mit asymptotischer Analyse ergibt. Es gibt mehrere mögliche Antworten, warum dieses Material in Einführungskursen unterrichtet wird:

  • Die asymptotische Analyse ist eine mathematische Abstraktion, die sich der Analyse ergibt. Als (wohl) Mathematiker wollen wir in der Lage sein, Algorithmen zu analysieren, und sie können ihre Komplexität nur durch asymptotische Analyse beherrschen.

  • Die Bewertung der asymptotischen Leistung eines Algorithmus zeigt einige in der Praxis nützliche Prinzipien auf: Konzentrieren Sie sich beispielsweise auf den Teil des Codes, der die meiste Zeit in Anspruch nimmt, und schließen Sie jeden Teil des Codes aus, der einen asymptotisch vernachlässigbaren Teil der Zeit in Anspruch nimmt .

  • Einige der Techniken der asymptotischen Analyse sind nützlich. Ich beziehe mich hier hauptsächlich auf den sogenannten "Hauptsatz", der unter vielen Umständen eine gute Beschreibung der Realität ist.

  • Es gibt auch einen historischen Grund: Als die Menschen mit der Analyse von Algorithmen begannen, dachten sie ernsthaft, dass die asymptotische Komplexität den praktischen Gebrauch widerspiegelt. Schließlich wurden sie jedoch als falsch erwiesen. Dasselbe geschah mit P als Klasse effizient lösbarer Probleme und NP als Klasse schwer lösbarer Probleme, die beide in der Praxis irreführend sind.

Persönlich denke ich, dass die asymptotische Analyse ein vernünftiger Bestandteil des Lehrplans ist. Fragwürdigere Teile sind die formale Sprachtheorie und die Komplexitätstheorie (alles, was mit einer Turing-Maschine zu tun hat). Einige Leute argumentieren, dass diese Themen zwar für den angehenden Programmierer per se nicht nützlich sind, ihr jedoch einen bestimmten Gedanken einflößen, der notwendig ist, um ein guter Praktiker zu sein. Andere argumentieren, dass die Theorie manchmal die Praxis beeinflusst, und diese seltenen Fälle sind genug, um zu rechtfertigen, diese eher arkanen Fächer dem allgemeinen Informatikpublikum zu vermitteln. Ich möchte lieber, dass sie Geschichte oder Literatur oder ein anderes Fach lernen, an dem sie tatsächlich interessiert sind. beide sind für ihre zukünftigen beruflichen Perspektiven ebenso relevant und für sie wichtiger als für den Menschen.

Yuval Filmus
quelle
Vielen Dank Yuval. Die Motivation ist in erster Linie, wie man den Schülern den Nutzen der asymptotischen Analyse und ihre Relevanz für die Praxis des Entwurfs und der Verwendung von Algorithmen in realen Anwendungen erklären kann (wobei in den meisten Fällen klar ist, dass wir nur an einer Endlichkeit interessiert sind, obwohl dies möglich ist sehr viele Instanzen), die den Lehrplan nicht rechtfertigen.
Kaveh
1
Ich bin verwirrt von Ihrer Prämisse. Sie scheinen davon auszugehen, dass die Zielgruppe sowohl Mathematiker als auch angehende Programmierer sind. Dies ist eine komische Kombination, die Informatiker nicht auszeichnet. (Ich teile auch nicht Ihre Meinung zu formalen Sprachen, aber das ist ein anderes Thema.)
Raphael
Im Gegenteil, ich gehe davon aus, dass die Zielgruppe aufstrebende Programmierer sind. Ein Großteil des Lehrplans dient jedoch theoretischen Informatikern. Natürlich haben diese beiden Gruppen widersprüchliche Bedürfnisse. Da die meisten Studenten angehende Programmierer sind, denke ich, dass der Lehrplan auf sie ausgerichtet sein sollte, aber einige Akademiker sind anderer Meinung. Vielleicht wollen sie die zukünftigen Professoren unterrichten. Vielleicht kannst du ihren Standpunkt erklären.
Yuval Filmus
3
@YuvalFilmus Ich habe oft erklärt, dass ich nicht glaube, dass CS = TCS + Programmierung. Wenn Sie einen CS-Kurs (an einer Universität) unterrichten und die meisten Ihrer Studenten Programmierer werden möchten, ist etwas kaputt (imho). Ich würde argumentieren, dass jeder Informatiker von einer soliden Ausbildung in Algorithmen, formalen Sprachen und sogar Komplexitätstheorien (und vielen anderen Dingen wie der Funktionsweise von Compilern und CPUs) profitieren kann.
Raphael
2
@Wildcard Computerarchitektur, Computergrafik, KI, Programmiersprachenforschung, ... - die Liste ist endlos! TCS ist wirklich eine Nische, und Programmierung ist nur ein Werkzeug für (die meisten) CS-Forscher.
Raphael
7

Es gibt zwei schwerwiegende Gründe, die Laufzeiten asymptotisch zu analysieren:

  • unwichtige Details zu abstrahieren. In vielen Anwendungen, in denen nicht-triviale Algorithmen erforderlich sind, wird die meiste Zeit für Probleminstanzen aufgewendet, die eine mittlere bis große Anzahl von Vorgängen erfordern, und wir sind mehr am allgemeinen Trend als an der genauen Anzahl von Vorgängen interessiert. In diesen Anwendungen ist das Verhalten für kleine uninteressant.n

  • mathematische Traktabilität zu ermöglichen. Ausnahmefälle, in denen es möglich ist, genaue Ausdrücke für die Anzahl der Vorgänge zu finden. Das Studium der Asymptotik eröffnet mehr Möglichkeiten (zum Beispiel sind asymptotische Approximationen komplizierter Funktionen praktisch).

Und es gibt viele andere (wie Maschinenunabhängigkeit, Aussagekraft, Vergleichbarkeit ...).

Yves Daoust
quelle
"Wir interessieren uns mehr für den allgemeinen Trend als für die genaue Anzahl der Operationen" - dieser Satz ist nicht allgemeingültig. Es ist eine Lehrbuchbegründung, die nicht in allen Anwendungen Gültigkeit hat. "Algorithmusoptimierung ist nützlich für mittlere bis große Anzahl von Operationen" - auch dies nicht. Ein Algorithmus, der immer auf kleinen Eingaben ausgeführt wird und schnell ist, aber milliardenfach ausgeführt wird, ist ebenfalls eine Optimierung wert. Praktisches Beispiel: Jede reale Quicksort-Implementierung wechselt zu einem anderen Sortieralgorithmus für kleine . n
Raphael
Nun, ich glaube nicht, dass es überhaupt eine Regel ist. Je mehr Daten Sie wegwerfen, desto schwächer werden die Aussagen, die Sie machen können. Die asymptotische (und vor allem "big-oh" -Perspektive) erzeugt Aussagen wie "Quicksort ist schneller als Insertionsort", was, wenn nicht falsch, auch nicht ganz richtig ist. (Ja, ich sage, Algorithmus-Analyse wird oft falsch gelehrt, imho.)
Raphael
6

Wie in Raphaels Antwort erwähnt, kann die exakte Berechnung der Worst-Case-Laufzeit sehr schwierig sein. Eine genaue Berechnung kann auch unnötig sein, da das RAM-Modell bereits Annäherungen einführt. Nehmen zum Beispiel alle Operationen wirklich die gleiche Zeit in Anspruch? Bestimmte Implementierungen (Hardware, Optimierungen) können einen Algorithmus durch konstante Faktoren beschleunigen. Wir wollen verstehen, wie effektiv ein Algorithmus unabhängig von diesen Faktoren ist. Dies ist eine große Motivation für den Einsatz der asymptotischen Analyse.

Juho
quelle
3

Weil die Asymptotik "einfach" ist (na ja, einfacher als die exakte Analyse für endliche Fälle).

Vergleichen Sie zB die Enzyklopädie "The Art of Computer Programming" von Knuth, in der alle wichtigen (und viele weniger wichtigen) Algorithmen detailliert analysiert werden, mit der Faustregelanalyse, die häufig ausreicht, um eine asymptotische Schätzung zu erhalten ( oder nur eine Grenze), wie es in den meisten "Algorithmen" -Büchern praktiziert wird.

Sie haben sicherlich recht. Wenn das Problem wichtig genug ist, kann eine Analyse nach Knuth-Art (oder etwas weniger detailliert) durchaus gerechtfertigt sein. In vielen Fällen reicht ein Hinweis auf die asymptotische Komplexität (möglicherweise Durchschnitt mit Dispersion), die den experimentellen Daten entspricht. In den meisten Fällen kann der Vergleich von Asymptotika als erste Unkrautrunde genau genug sein , um eine grobe Klassifizierung konkurrierender Algorithmen vorzunehmen. Und wenn es keine Konkurrenten gibt, ist es nur Masochismus, die schlechten Nachrichten über die genauen Kosten bis ins kleinste Detail zu erhalten.

vonbrand
quelle
2
Dies ist nur die halbe Wahrheit: Zunächst scheint es, dass Sie mit dem Gedanken an "big-oh" schreiben (was in der Frage nicht erwähnt wird). Zweitens sind "Big-Oh" -Asymptoten dafür bekannt, dass sie bei der Auswahl von Algorithmen spektakulär für "Unkraut-Runden" versagen: Eingaben sind in der Realität endlich.
Raphael
3

Mit asymptotischer Analyse meine ich hier das Verhalten des Algorithmus, wenn die Größe der Eingabe unendlich wird.

Der Grund, warum wir die asymptotische Analyse verwenden, ist, dass sie für die Vorhersage des Verhaltens von Algorithmen in der Praxis nützlich ist . Die Vorhersagen erlauben uns Entscheidungen zu treffen, zB wenn wir unterschiedliche Algorithmen für ein Problem haben, welches sollten wir verwenden? (Nützlich zu sein bedeutet nicht, dass es immer richtig ist.)

Dieselbe Frage kann über jedes vereinfachte Modell der realen Welt gestellt werden. Warum verwenden wir vereinfachte mathematische Modelle der realen Welt?

Denken Sie an Physik. Die klassische Newtonsche Physik ist bei der Vorhersage der realen Welt nicht so gut wie die relativistische Physik. Aber es ist ein Modell, das gut genug ist, um Autos, Wolkenkratzer, U-Boote, Flugzeuge, Brücken usw. zu bauen. Es gibt Fälle, in denen es nicht gut genug ist, z. B. wenn wir einen Satelliten bauen oder eine Raumsonde an Pluto senden oder die Bewegung vorhersagen möchten von massiven Himmelsobjekten wie Sternen und Planeten oder sehr schnellen Objekten wie Elektronen. Es ist wichtig zu wissen, wo die Grenzen eines Modells liegen.

  1. Dies ist normalerweise eine hinreichende Annäherung an die reale Welt. In der Praxis sehen wir oft, dass ein Algorithmus mit besserer asymptotischer Analyse in der Praxis besser funktioniert. Es kommt selten vor, dass ein Algorithmus ein besseres asymptotisches Verhalten aufweist. Wenn die Eingaben also groß genug sind, können wir uns in der Regel auf die asymptotische Analyse als erste Vorhersage des Verhaltens des Algorithmus verlassen. Es ist nicht so, wenn wir wissen, dass die Eingaben klein sein werden. Abhängig von der gewünschten Leistung müssen wir möglicherweise eine genauere Analyse durchführen. Wenn wir beispielsweise Informationen über die Verteilung der Eingaben haben, die dem Algorithmus mitgeteilt werden, können wir eine genauere Analyse durchführen, um die Ziele zu erreichen, die wir haben (z. B. schnell auf 99) % der Eingänge). Der Punkt ist, als erster Schritt, die asymptotische Analyse ist ein guter Ausgangspunkt. In der Praxis sollten wir auch Leistungstests durchführen, aber bedenken Sie, dass dies auch seine eigenen Probleme hat.

  2. In der Praxis ist die Berechnung relativ einfach. Typischerweise können wir zumindest gute Grenzen für die asymptotische Komplexität eines Algorithmus berechnen. Der Einfachheit halber nehmen wir an, dass wir einen Algorithmus , der jeden anderen Algorithmus bei jeder Eingabe übertrifft. Wie können wir wissen, dass besser ist als andere? Wir können asymptotische Analysen durchführen und feststellen, dassA AAAAhat eine bessere asymptotische Komplexität. Was ist in allen Eingaben besser als das andere? Dann wird es kniffliger und hängt davon ab, was uns wichtig ist. Interessieren uns große oder kleine Eingaben? Wenn wir uns um große Eingaben kümmern, ist es nicht üblich, dass ein Algorithmus eine bessere asymptotische Komplexität aufweist, sich jedoch bei großen Eingaben, die uns wichtig sind, am schlechtesten verhält. Wenn wir uns mehr für kleine Eingaben interessieren, ist eine asymptotische Analyse möglicherweise nicht so nützlich. Wir sollten die Laufzeit der Algorithmen auf Eingaben vergleichen, die uns interessieren. In der Praxis ist eine asymptotische Analyse für komplizierte Aufgaben mit komplizierten Anforderungen möglicherweise nicht so nützlich. Für einfache Grundprobleme, die in Algorithmus-Lehrbüchern behandelt werden, ist es sehr nützlich.

Kurz gesagt ist asymptotische Komplexität eine relativ einfach zu berechnende Approximation der tatsächlichen Komplexität von Algorithmen für einfache Grundaufgaben (Probleme in einem Algorithmenlehrbuch). Wenn wir kompliziertere Programme erstellen, ändern sich die Leistungsanforderungen und werden komplizierter, und die asymptotische Analyse ist möglicherweise nicht so nützlich.


Es ist gut, die asymptotische Analyse mit anderen Ansätzen zu vergleichen, um die Leistung von Algorithmen vorherzusagen und zu vergleichen. Ein gängiger Ansatz sind Leistungstests anhand von Zufalls- oder Benchmark-Eingaben. Dies ist häufig der Fall, wenn die Berechnung der asymptotischen Komplexität schwierig oder nicht durchführbar ist, z. B. wenn wir Heuristiken wie die SAT-Lösung verwenden. Ein anderer Fall ist, wenn die Anforderungen komplizierter sind, z. B. wenn die Leistung eines Programms von externen Faktoren abhängt und unser Ziel möglicherweise darin besteht, dass auf 99% der Websites eine zeitlich begrenzte Aktualisierung der Benutzeroberfläche durchgeführt wird Eingänge.

Beachten Sie jedoch, dass die Leistungsanalyse auch Probleme mit sich bringt. Es gibt keine mathematischen Anhaltspunkte für die Leistung bei weniger. Wir führen den Leistungstest tatsächlich für alle Eingaben durch, die an den Algorithmus gegeben werden (oft rechnerisch nicht umsetzbar) (und es ist oft nicht möglich, zu entscheiden, dass einige Eingaben niemals gegeben werden). Wenn wir mit einer Zufallsstichprobe oder einem Benchmark testen, gehen wir implizit von einer gewissen Regelmäßigkeit in Bezug auf die Leistung der Algorithmen aus, dh der Algorithmus wird bei anderen Eingaben, die nicht Teil des Leistungstests waren, eine ähnliche Leistung erbringen.

Das zweite Problem bei Leistungstests ist, dass sie von der Testumgebung abhängen. Das heißt, die Leistung eines Programms wird nicht allein durch die Eingaben bestimmt, sondern durch äußere Faktoren (z. B. Maschinentyp, Betriebssystem, Effizienz des codierten Algorithmus, Auslastung der CPU, Speicherzugriffszeiten usw.), von denen einige zwischen verschiedenen Durchläufen variieren können der Test auf der gleichen Maschine. Auch hier gehen wir davon aus, dass die bestimmten Umgebungen, in denen Leistungstests durchgeführt werden, der tatsächlichen Umgebung ähnlich sind, es sei denn, wir führen die Leistungstests in allen Umgebungen durch, in denen das Programm ausgeführt werden kann (und wie können wir vorhersagen, auf welchen Computern eine Sortierung ausgeführt werden könnte Algorithmus in 10 Jahren an?).

Vergleichen Sie diese mit der Berechnung der asymptotischen Laufzeit von say MergeSort ( ) und vergleichen Sie sie mit der Laufzeit von say SelectionSort ( ) oder BinarySerch ( ) mit LinearSearch ( ).Θ ( n 2 ) Θ ( lg n ) O ( n )Θ(nlgn)Θ(n2)Θ(lgn)O(n)

Kaveh
quelle
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Raphael
Ich mag diese Antwort genug, um jetzt zu stimmen. Zwei Anmerkungen: 1) Ich würde hier "Kosten" anstelle von "Komplexität" verwenden. Teilweise aus Gründen der Tiergesundheit, aber auch, weil viele Kostenmaßnahmen denkbar sind (was alle von Ihnen genannten Überlegungen erschwert). 2) Möglicherweise möchten Sie einen Sprachpass machen. ;)
Raphael
@ Raffael, danke. Ich plane bald eine weitere Bearbeitung. :)
Kaveh
-2

O(n2)O(nlogn)O(n2) damit es im vergleich zu quicksort endet.

Stellen Sie sich nun vor, dass im Code so oft gewartet wird, wie der Code aufgerufen wird. Wie kann man diese scheinbare Überlegenheit des Quicksort-Algorithmus mathematisch quantifizieren / begründen? (Ist der Name wirklich gerechtfertigt oder ist er nur ein Marketing-Slogan?) über asymptotische Komplexitätsmessungen. Wenn man sich die Animationen anschaut, hat man das subjektive Gefühl, dass Bubblesort irgendwie ein schwächerer Algorithmus ist, und die asymptotische Komplexitätsanalyse kann dies quantitativ belegen . Beachten Sie jedoch, dass die asymptotische Komplexitätsanalyse nur ein Werkzeug in der Tasche von Werkzeugen zur Analyse von Algorithmen ist und nicht immer das ultimative.

und es lohnt sich auch, den Side-by-Side-Code zu betrachten. bubblesort scheint konzeptionell einfacher zu sein und verwendet keine Rekursion. quicksort ist nicht so unmittelbar zu verstehen, vor allem das "Median of 3" -Pivot-Prinzip. bubblesort kann nur in Schleifen ohne Subroutine implementiert werden, während quicksort normalerweise mindestens eine Subroutine hat. Dies zeigt das Muster, dass mehr Code-Raffinesse manchmal die asymptotische Komplexität auf Kosten der Code-Einfachheit verbessern kann. Manchmal gibt es einen extremen Kompromiss, der dem Konzept der Verringerung der Grenzerträge (ursprünglich aus der Wirtschaft) ähnelt, bei dem sehr große Mengen an Code-Komplexität (die ganze Papiere voller Thms und Beweise erfordern, um dies zu rechtfertigen) nur sehr kleine Verbesserungen der asymptotischen Komplexität bewirken. Dies zeigt sich als Beispiel insb. mitMatrixmultiplikation und kann sogar grafisch dargestellt werden .

vzn
quelle
Zwischen "Betrachten von Animationen" und formaler Analyse wie umfangreichen Laufzeitbenchmarks liegt viel Raum. Sie sind tatsächlich ein gültiger Bereich für sich, da wir nicht über die Theorie verfügen, um all die Dinge zu erklären, die die Laufzeiten beeinflussen.
Raphael
@raphael Sie haben das Benchmarking in Ihrer Antwort behandelt. Es ist eine gute Antwort. Beachten Sie jedoch, dass Animation / Visualisierung in engem Zusammenhang mit Benchmarking stehen kann. Tatsächlich gibt es eine Menge Erklärungen, was die Laufzeiten beeinflusst, aber bis zu einem gewissen Grad glättet / mittelt das "Rauschen" und die asymptotische Komplexität das Rauschen. das ist eine andere Übung, um zu sehen, wie es das tatsächlich macht.
VZN
Animationen filtern jedoch kein Rauschen heraus. Außerdem ist das menschliche Auge leicht zu täuschen, und es ist einfach nicht möglich, Animationen für eine Stichprobe von Listen mit angemessener Größe (z. B. 1000 Listen für Größen in Millionen, um Sortieralgorithmen zu bewerten) anzusehen und zu entscheiden, welcher Algorithmus schneller war (im Durchschnitt).
Raphael
nn
n