Wie kann ich bei der Berechnung der Laufzeitkomplexität die grundlegende Operation herausfinden?

Question

Ich versuche, die schlechteste Laufzeitkomplexität für eine Reihe von Algorithmen zu ermitteln. Ich bin jedoch auf das Problem gestoßen, dass ich immer wieder dazu neige, die falsche oder eine falsche Anzahl von Grundoperationen für einen Algorithmus auszuwählen.

Mir scheint, dass die Auswahl der grundlegenden Operation eher eine Kunst als eine Wissenschaft ist. Nachdem ich gegoogelt und meine Textboxen gelesen habe, habe ich immer noch keine gute Definition gefunden. Bislang habe ich sie definiert als "eine Operation, die bei der Ausführung eines Algorithmus immer vorkommt", z. B. ein Vergleich oder eine Array-Manipulation.

Aber Algorithmen haben oft viele Vergleiche, die immer ausgeführt werden, also welche Operation wählt man?

Answer 1

Ich stimme zu, dass es bis zu einem gewissen Grad eine Kunst ist, daher sollte man beim Schreiben von Dokumentationen usw. immer Klarheit schaffen. Aber normalerweise ist es ein "Besuch" der zugrunde liegenden Datenstruktur. Wie Sie schon sagten, handelt es sich bei einem Array um einen Vergleich oder eine Vertauschung, bei einer Hash-Map kann es sich um eine manuelle Prüfung eines Schlüssels handeln, bei einem Graphen ist es ein Besuch eines Vertex oder einer Kante usw.

Answer 2

Selbst praktizierende Komplexitätstheoretiker sind sich in dieser Hinsicht uneinig, so dass die folgenden Ausführungen vielleicht etwas subjektiv sind: http://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html

Der Zweck der Big-O-Notation besteht darin, die Effizienz eines Algorithmus für den Leser zusammenzufassen. In der Praxis interessiert mich am meisten, wie viele Taktzyklen ein Algorithmus benötigt, wobei ich davon ausgehe, dass die Big-O-Konstante weder extrem klein noch groß ist (und die Auswirkungen der Speicherhierarchie ignoriere); dies ist das "Einheitskosten"-Modell, auf das im verlinkten Beitrag angespielt wird.

Der Grund für die Zählung von Vergleichen bei Sortieralgorithmen ist, dass die Kosten eines Vergleichs von der Art der Eingabedaten abhängen. Man könnte sagen, dass ein Sortieralgorithmus O(c n log n) Zyklen benötigt, wobei c der Aufwand für einen Vergleich ist, aber es ist in diesem Fall einfacher, stattdessen Vergleiche zu zählen, da die andere vom Algorithmus durchgeführte Arbeit O(n log n) ist. Es gibt einen Sortieralgorithmus, der die Verkettung von n sortierten Arrays der Länge n in n^2 log n Schritten und n^2 Vergleichen sortiert; hier würde ich erwarten, dass die Anzahl der Vergleiche und der Rechenaufwand separat angegeben werden, da keiner der beiden notwendigerweise den anderen dominiert.

Answer 3

Das funktioniert nur, wenn Sie den Algorithmus tatsächlich implementiert haben, aber Sie könnten einfach einen Profiler verwenden, um zu sehen, welche Operation der Engpass ist. Das ist eine praktische Sichtweise. In der Theorie gehen manche davon aus, dass alles, was nicht die grundlegende Operation ist, in Nullzeit läuft.

Answer 4

Die recht einfache Definition, die ich gehört habe, lautet:

Der Vorgang, der mindestens so oft ausgeführt wird wie Operation im Algorithmus ausgeführt wird.

Bei einem Sortieralgorithmus beispielsweise handelt es sich eher um Vergleiche als um Zuweisungen, da ein Element fast immer besucht und "geprüft" werden muss, bevor es neu geordnet wird, wobei die Prüfung nicht unbedingt zu einer Neuordnung führt. Es wird also immer mindestens so viele Vergleiche wie Zuweisungen geben.