Gibt es echte Algorithmen, die in der folgenden Klasse weit überdurchschnittlich gut abschneiden? [geschlossen]

39

Letzte Nacht habe ich mit einem anderen Programmierer besprochen, dass eine Operation, die O (n) ist, möglicherweise die Leistung von O (1) übertrifft, wenn der O (1) -Algorithmus eine große Konstante enthält. Er war anderer Meinung, also habe ich es hierher gebracht.

Gibt es Beispiele für Algorithmen, die die in der darunter liegenden Klasse weit übertreffen? Beispielsweise ist O (n) schneller als O (1) oder O (n 2 ) schneller als O (n).

Mathematisch kann dies für eine Funktion mit einer asymptotischen Obergrenze demonstriert werden, wenn Sie konstante Faktoren außer Acht lassen. Existieren solche Algorithmen jedoch in der Natur? Und wo würde ich Beispiele dafür finden? Für welche Arten von Situationen werden sie verwendet?

KyleWpppd
quelle
15
Auch für "große" Algorithmen ist kleiner nicht unbedingt besser. Zum Beispiel ist die Gaußsche Eliminierung O (n ^ 3), aber es gibt Algorithmen, die dies in O (n ^ 2) tun können, aber der Koeffizient für das quadratische Zeit-Algo ist so groß, dass die Leute einfach mit O (n ^ gehen 3) eins.
Blackjack
11
Sie müssen "... für Probleme in der realen Welt" oder solche hinzufügen, um dies zu einer vernünftigen Frage zu machen. Andernfalls müssen Sie nur ngroß genug machen, um die Konstante zu kompensieren (was der Punkt der Big-O-Notation ist).
Starblue
8
Nehmen Sie keine Big-O-Notation für Geschwindigkeit.
Codism
16
Bei der Big-O-Notation geht es nicht darum, wie schnell ein Algorithmus ausgeführt wird, sondern darum, wie gut er skaliert.
BlueRaja - Danny Pflughoeft
4
Ich bin überrascht, dass niemand den Simplex-Algorithmus zum Lösen von LP erwähnt hat. Es hat einen exponentiellen Worst-Case mit einer linearen erwarteten Laufzeit. In der Praxis ist es ziemlich schnell. Es ist trivial, ein Problem zu konstruieren, das auch die Laufzeit im schlimmsten Fall aufweist. Auch ist es stark genutzt.
Ccoakley

Antworten:

45

Suchvorgänge in sehr kleinen, festen Datentabellen. Eine optimierte Hash-Tabelle kann 0 (1) sein und dennoch aufgrund der Kosten der Hash-Berechnung langsamer als eine binäre Suche oder sogar eine lineare Suche.

Loren Pechtel
quelle
14
Genauer gesagt ist die Hashtabellensuche O (m), wobei m die Größe des Schlüssels ist. Sie können dieses O (1) nur aufrufen, wenn die Schlüsselgröße konstant ist. Normalerweise ist das auch amortisiert - sonst kann der Tisch nicht wachsen / schrumpfen. Ternäre Bäume können häufig Hash-Tabellen für String-Lookups unterbieten, in denen die Strings nicht oft gefunden werden. Bei der Suche nach ternären Bäumen wird häufig festgestellt, dass der Schlüssel nicht vorhanden ist, während das oder die ersten Zeichen des Strings überprüft werden hashtable version hat den Hash noch nicht berechnet.
Steve314
2
Ich liebe die Antwort von Loren Pechtel und den ersten Kommentar von Steve314. Ich habe das tatsächlich gesehen. Wenn Sie eine Java-Klasse mit einer hashcode () -Methode erstellen, die zu lange dauert, um den Hash-Wert zurückzugeben (und ihn nicht zwischenspeichern kann / kann), verwenden Sie Instanzen einer solchen Klasse in einer Sammlung vom Typ Hash (z. B.) HashSet) macht diese Sammlung VIEL langsamer als eine Array-Typ-Sammlung (wie ArrayList).
Shivan Dragon
1
@ Steve314: warum nimmst du an, dass Hash-Funktionen O (m) sind, wobei m die Größe des Schlüssels ist? Hash-Funktionen können O (1) sein, auch wenn Sie sich mit Zeichenfolgen (oder einem anderen komplexen Typ) befassen. Es gibt keinen zu großen Wert für die formale Definition, als dass die einfache Realisierung der Hash-Funktion die Komplexität erheblich verändern könnte, wenn für Ihre Eingabe eine falsche Datenstruktur (Hash-Tabelle) gewählt wird (die Schlüsselgröße ist nicht vorhersehbar).
Codism
1
@ Steve314: Beachten Sie, dass ich feste Datentabellen sagte. Sie wachsen nicht. Außerdem erhalten Sie nur dann eine O (1) -Leistung aus einer Hash-Tabelle, wenn Sie den Schlüssel optimieren können, um sicherzustellen, dass keine Kollisionen auftreten.
Loren Pechtel
1
@Loren - Wenn der Tisch eine feste Größe hat, können Sie stets maximal nach einem freien Platz suchen. Das heißt, Sie müssen höchstens n-1 bereits ausgefüllte Slots prüfen, wobei n die konstante Tabellengröße ist. Eine Hash-Tabelle mit fester Größe ist also tatsächlich O (1), ohne dass eine amortisierte Analyse erforderlich ist. Das bedeutet nicht, dass es Ihnen egal ist, ob die Zugriffe langsamer werden, wenn der Tisch voll ist - nur, dass es nicht das ist, was O ausdrückt.
Steve314
25

Matrix-Multiplikation. Der naive O (n ^ 3) -Algorithmus wird in der Praxis häufig schneller als Strassens O (n ^ 2.8) für kleinräumige Matrizen verwendet. und Strassen wird anstelle des O (n ^ 2.3) -Coppersmith-Winograd-Algorithmus für größere Matrizen verwendet.

Peter Taylor
quelle
2
Kupferschmied-Winograd wird NIE verwendet. Die Implementierung wäre eine schreckliche Aufgabe für sich und die Konstante ist so schlecht, dass sie selbst für moderne wissenschaftliche Matrixprobleme nicht durchführbar wäre.
tskuzzy
24

Ein einfaches Beispiel ist der Unterschied zwischen verschiedenen Sortieralgorithmen. Mergesort, Heapsort und einige andere sind O (n log n) . Quicksort ist der schlechteste Fall von O (n ^ 2) . Aber oft ist Quicksort schneller und arbeitet im Durchschnitt wie O (n log n) . Mehr Infos .

Ein anderes Beispiel ist die Erzeugung einer einzelnen Fibonacci-Zahl. Der iterative Algorithmus ist O (n) , während der matrixbasierte Algorithmus O (log n) ist . Dennoch ist der iterative Algorithmus für die ersten paar tausend Fibonacci-Zahlen wahrscheinlich schneller. Das kommt natürlich auch auf die Umsetzung an!

Algorithmen mit einer besseren asymptotischen Leistung können kostspielige Operationen enthalten, die bei einem Algorithmus mit schlechterer Leistung, aber einfacheren Operationen nicht erforderlich sind. Am Ende sagt die O- Anmerkung nur dann etwas über die Leistung aus, wenn das Argument, mit dem sie arbeitet, dramatisch zunimmt (gegen unendlich geht).

molf
quelle
Dies ist eine großartige Erklärung für Big-O, die sich jedoch nicht mit dem Kern der Frage befasst. Dies gilt insbesondere für Fälle, in denen ein O (n) -Algorithmus schneller ist als ein O (1).
KyleWpppd
Die Fibonacci Nummer eins ist leicht daneben. Die Ausgabegröße ist exponentiell in der Eingabegröße, daher besteht ein Unterschied zwischen O (lg n * e ^ n) und O (lg lg n * e ^ n).
Peter Taylor
Nachtrag: bestenfalls. Der matrixbasierte Algorithmus multipliziert mit Zahlen in der Größenordnung von 1,5 ^ n, sodass O (lg lg n * ne ^ n) die beste nachweisbare Bindung sein könnte.
Peter Taylor
1
Quicksort wird normalerweise sowieso als O (n log n) erwartete Leistung beschrieben - der schlimmste Fall ist für zufällige Eingaben ziemlich unwahrscheinlich, und der Einbau von Zufälligkeiten in einen Prepass oder in die Pivot-Auswahl bedeutet, dass der schlimmste Fall für signifikante Eingabegrößen insgesamt sehr unwahrscheinlich ist. Der Worst-Case ist weniger relevant als die Tatsache, dass Quicksort (1) sehr einfach und (2) sehr cachefreundlich ist, was zu signifikant besseren konstanten Faktoren führt als bei vielen anderen Sortieralgorithmen.
Steve314
(2) ist genau die Art von externer Überlegung, die bei der Betrachtung der Big-O-Leistung berücksichtigt werden muss. Algorithmisch sollte Mergesort Quicksort immer übertreffen, aber die Ressourcennutzung und die Cache-Lokalität kehren im Allgemeinen ihre realen Leistungspositionen um.
Dan Lyons
18

Hinweis: Bitte lesen Sie die Kommentare von @ back2dos und anderen Gurus, da sie in der Tat hilfreicher sind als das, was ich geschrieben habe. Vielen Dank für alle Mitwirkenden.

Ich denke aus der folgenden Tabelle (entnommen aus: Big O-Notation , suche nach "The Pessimistic Nature of Algorithms:"), dass O (log n) nicht immer besser ist, als zu sagen, O (n). Also, ich denke, dein Argument ist gültig.

Bild-1

Emmad Kareem
quelle
6
Die Frage wollte konkrete Beispiele für Algorithmen aus der Praxis. Das hat keiner so wie es ist.
Megan Walker
19
Sie können in dieser Grafik nichts sehen, was die Frage beantworten würde. Es ist irreführend. Dieser Graph lediglich zeichnet die Funktionen y = 1, y = log xund so weiter und die Kreuzung von y = 1und y = xist eigentlich der Punkt (1,1). Wenn dies wirklich richtig wäre, würde man sagen, dass Algorithmen mit höherer Komplexität für 0 bis 2 Einträge schneller sein können, was die Leute kaum interessieren würden. Was in der Grafik völlig außer Acht gelassen wird (und woraus der wahrnehmbare Leistungsunterschied resultiert), sind konstante Faktoren.
back2dos
@ Samuel Walker, danke für den Kommentar. Der bereitgestellte Link (Link-1) enthält einige Beispiele für Algorithmen pro Kategorie.
NoChance
5
@ back2dos: Das Diagramm allein beantwortet die Frage nicht, kann aber verwendet werden, um sie zu beantworten. Die Form jeder angezeigten Funktion ist für alle Maßstäbe und konstanten Faktoren gleich. Damit zeigt die Grafik, dass es bei gegebener Funktionskombination einen Bereich von Eingängen gibt, für den einer kleiner ist, und einen Bereich von Eingängen, für den der andere ist.
Jan Hudec
2
@dan_waterworth, du hast recht, ich gebe diesen Punkt zu und entferne diesen Kommentar. Dennoch ist die Antwort in zweierlei Hinsicht falsch oder irreführend: 1) Der springende Punkt von Big-O ist, dass es eine Obergrenze für die Komplexität gibt; Dies ist nur für große n sinnvoll, da wir mit zunehmendem n explizit kleinere Terme ausschließen, die vom größten Term überfordert werden. 2) Es geht darum, Beispiele für zwei Algorithmen zu finden, bei denen der Algorithmus mit der höheren Big-O-Bindung den Algorithmus mit der niedrigeren übertrifft. Diese Antwort schlägt fehl, weil es keine solchen Beispiele gibt.
Caleb
11

Für praktische Werte von nja. Dies kommt in der CS-Theorie häufig vor. Oft gibt es einen komplizierten Algorithmus mit technisch besserer Big-Oh-Leistung, aber die konstanten Faktoren sind so groß, dass sie unpraktisch werden.

Mein Professor für Computergeometrie hatte einmal einen Algorithmus zur Triangulation eines Polygons in linearer Zeit beschrieben, aber er schloss mit "sehr kompliziert. Ich glaube, niemand hat ihn tatsächlich implementiert" (!!).

Auch Fibonacci-Haufen haben bessere Eigenschaften als normale Haufen, sind aber nicht sehr beliebt, da sie in der Praxis nicht so gut funktionieren wie normale Haufen. Dies kann auf andere Algorithmen übergehen, die Heaps verwenden - beispielsweise ist Dijkstras kürzester Pfad mit einem Fibonacci-Heap mathematisch schneller, in der Praxis jedoch normalerweise nicht.

Gabe Moothart
quelle
Bei großen Diagrammen in der Größenordnung von etwa 100.000 Eckpunkten ist dies schneller.
tskuzzy
Fibonacci-Haufen waren auch mein erster (eigentlich zweiter) Gedanke.
Konrad Rudolph
10

Vergleichen Sie das Einfügen in eine verknüpfte Liste und das Einfügen in ein Array mit geänderter Größe.

Die Datenmenge muss ziemlich groß sein, damit sich das Einfügen der verknüpften Liste O (1) lohnt.

Eine verknüpfte Liste hat zusätzlichen Overhead für die nächsten Zeiger und Dereferenzen. Ein Array mit veränderbarer Größe muss Daten kopieren. Das Kopieren ist O (n), aber in der Praxis sehr schnell.

Winston Ewert
quelle
1
Die Größe eines anpassbaren Arrays wird bei jedem Füllen verdoppelt, sodass die durchschnittlichen Kosten für das Anpassen der Größe pro Einfügung 0 (1) betragen.
Kevin Cline
2
@ kevincline, ja, aber das O (n) entsteht, wenn alle Elemente nach der Einfügemarke nach vorne verschoben werden müssen. Die Allokation wird 0 (1) Mal abgeschrieben. Mein Punkt ist, dass diese Bewegung immer noch sehr schnell ist, so dass in der Praxis normalerweise verknüpfte Listen übertroffen werden.
Winston Ewert
Der Grund, warum zusammenhängende Arrays im Vergleich zu verknüpften Listen so schnell sind, liegt im Prozessor-Caching. Das Durchlaufen einer verknüpften Liste führt zu einem Cache-Fehler für jedes Element. Um das Beste aus beiden Welten herauszuholen, sollten Sie eine nicht aufgerollte verknüpfte Liste verwenden .
Dan_waterworth
Größenveränderbare Arrays kopieren nicht immer. Es hängt davon ab, worauf es läuft und ob irgendetwas im Weg ist. Gleiches gilt für die doppelte Größe, implementierungsspezifisch. Das Überrollen ist jedoch ein Problem. Verknüpfte Listen eignen sich in der Regel am besten für Warteschlangen unbekannter Größe, obwohl Rotationspuffer den Warteschlangen eine Chance geben. In anderen Fällen sind verknüpfte Listen nützlich, da durch Zuweisung oder Erweiterung nicht immer zusammenhängende Inhalte zur Verfügung stehen, sodass Sie ohnehin einen Zeiger benötigen.
jgmjgm
@jgmjgm, wenn Sie in die Mitte eines anpassbaren Arrays einfügen, werden die Elemente danach absolut kopiert.
Winston Ewert
8

Die Big-Oh-Notation wird verwendet, um die Wachstumsrate einer Funktion zu beschreiben. Daher ist es möglich, dass ein O (1) -Algorithmus schneller ist, jedoch nur bis zu einem bestimmten Punkt (dem konstanten Faktor).

Gemeinsame Notationen:

O (1) - Die Anzahl der Iterationen (manchmal können Sie dies als von der Funktion aufgewendete Benutzerzeit bezeichnen) hängt nicht von der Größe der Eingabe ab und ist tatsächlich konstant.

O (n) - Die Anzahl der Iterationen wächst linear mit der Größe der Eingabe. Bedeutung - Wenn der Algorithmus eine Eingabe N, 2 × N-mal durchläuft, wird er weiterhin als O (n) betrachtet.

O (n ^ 2) (quadratisch) - Die Anzahl der Iterationen ist das Quadrat der Eingabegröße.

Yam Marcovic
quelle
2
Um einer ansonsten ausgezeichneten Antwort ein Beispiel hinzuzufügen: Eine O (1) -Methode kann pro Aufruf 37 Jahre dauern, während eine O (n) -Methode pro Aufruf 16 * n Mikrosekunden dauern kann. Welche ist schneller?
Kaz Dragon
16
Ich verstehe überhaupt nicht, wie dies die Frage beantwortet.
Avakar
7
Ich verstehe Big-O. Die eigentliche Frage, bei der es sich um spezifische Beispiele für Funktionen handelt, bei denen Algorithmen mit einem niedrigeren Big-O von denen mit einem höheren Big-O übertroffen werden, wird hier nicht angesprochen.
KyleWpppd
Wenn Sie die Frage in das Formular "Gibt es Beispiele ..." eingeben, wird unweigerlich jemand mit "Ja" antworten. ohne irgendwelche zu geben.
Rakslice
1
@rakslice: Vielleicht schon. Diese Seite verlangt jedoch eine Erklärung (oder besser noch einen Beweis) aller Aussagen, die Sie machen. Nun ist der beste Weg, um zu beweisen, dass es solche Beispiele gibt, einen zu geben;)
back2dos
6

Regex-Bibliotheken werden normalerweise für das Backtracking implementiert, bei dem die Exponentialzeit im ungünstigsten Fall größer ist als bei der DFA-Generierung mit einer Komplexität von O(nm).

Naives Backtracking kann eine bessere Leistung erbringen, wenn die Eingabe auf der Überholspur bleibt oder fehlschlägt, ohne dass ein übermäßiges Backtracking erforderlich ist.

(Obwohl diese Entscheidung nicht nur auf der Leistung basiert, werden auch Rückverweise zugelassen.)

dan_waterworth
quelle
Ich denke, es ist auch teilweise historisch - der Algorithmus zum Umwandeln eines regulären Ausdrucks in einen DFA wurde patentiert, als einige der früheren Tools (sed und grep, denke ich) entwickelt wurden. Natürlich habe ich das von meinem Compilerprofessor gehört, der sich nicht ganz sicher war. Es handelt sich also um einen Bericht aus dritter Hand.
Tikhon Jelvis
5

Ein O(1)Algorithmus:

def constant_time_algorithm
  one_million = 1000 * 1000
  sleep(one_million) # seconds
end

Ein O(n)Algorithmus:

def linear_time_algorithm(n)
  sleep(n) # seconds
end

Für jeden Wert von nwhere n < one_millionist der O(n)im Beispiel angegebene Algorithmus eindeutig schneller als der O(1)Algorithmus.

Dieses Beispiel ist zwar ein bisschen scherzhaft, entspricht aber im Grunde dem folgenden Beispiel:

def constant_time_algorithm
  do_a_truckload_of_work_that_takes_forever_and_a_day
end

def linear_time_algorithm(n)
  i = 0
  while i < n
    i += 1
    do_a_minute_amount_of_work_that_takes_nanoseconds
  end
end

Sie müssen die Konstanten und Koeffizienten in Ihrem wissen OAusdruck, und Sie müssen den erwarteten Bereich von wissen n, um zu bestimmen , a priori , der Algorithmus schneller sein wird am Ende.

Andernfalls Sie müssen Benchmark die beiden Algorithmen mit Werten nim erwarteten Bereich , um zu bestimmen , a posteriori , die schneller ist beendet Algorithmus auf.

yfeldblum
quelle
4

Sortierung:

Die Einfügungssortierung ist O (n ^ 2), übertrifft jedoch andere O (n * log (n)) - Sortieralgorithmen für eine geringe Anzahl von Elementen.

Dies ist der Grund, warum die meisten Sortierimplementierungen eine Kombination aus zwei Algorithmen verwenden. Verwenden Sie beispielsweise die Zusammenführungssortierung, um große Arrays auf eine bestimmte Größe aufzuteilen, und verwenden Sie dann die Einfügesortierung, um die kleineren Einheiten zu sortieren und sie erneut mit der Zusammenführungssortierung zusammenzuführen.

Weitere Informationen finden Sie unter Timsort der aktuellen Standardimplementierung von Python- und Java 7-Sortierungen, die diese Technik verwenden.

OliverS
quelle
3

Bubblesort im Speicher kann die Leistung von QuickSort übertreffen, wenn das Programm auf die Festplatte ausgelagert wird oder wenn beim Vergleich alle Elemente von der Festplatte gelesen werden müssen.

Dies sollte ein Beispiel sein, auf das er sich beziehen kann.

user1249
quelle
Setzt die angegebene Komplexität von Quicksort und Bubblesort nicht einen zufälligen Speicherzugriff von O (1) voraus? Wenn dies nicht mehr der Fall ist, müsste dann die Komplexität von QuickSorts nicht erneut überprüft werden?
Viktor Dahl
@ViktorDahl, die Elementzugriffszeit ist nicht Teil dessen, was traditionell an der Komplexität des Sortieralgorithmus gemessen wird, daher ist "O (1)" hier nicht die richtige Wortwahl. Verwenden Sie stattdessen "konstante Zeit". PHK schrieb vor einiger Zeit einen Artikel über Sortieralgorithmen, in dem er wusste, dass das Abrufen einiger Elemente teurer ist als das Abrufen anderer (virtueller Speicher) - queue.acm.org/detail.cfm?id=1814327 - Sie könnten ihn interessant finden.
Ich sehe jetzt meinen Fehler. In der Regel misst man die Anzahl der Vergleiche und natürlich werden sie nicht von der Geschwindigkeit des Speichermediums beeinflusst. Danke auch für den Link.
Viktor Dahl
3

Häufig setzen die fortgeschritteneren Algorithmen einen gewissen (teuren) Installationsaufwand voraus. Wenn Sie es nur einmal ausführen müssen, ist die Brute-Force-Methode möglicherweise besser geeignet.

Beispiel: Die binäre Suche und die Suche nach Hashtabellen sind pro Suche viel schneller als die lineare Suche, Sie müssen jedoch die Liste sortieren bzw. die Hashtabelle erstellen.

Die Sortierung kostet Sie N log (N) und die Hash-Tabelle kostet mindestens N. Wenn Sie jetzt Hunderte oder Tausende von Suchvorgängen durchführen, ist dies immer noch eine amortisierte Einsparung. Wenn Sie jedoch nur ein oder zwei Suchvorgänge ausführen müssen, ist es möglicherweise sinnvoll, nur die lineare Suche durchzuführen und die Startkosten zu sparen.

Matthew Scouten
quelle
1

Die Entschlüsselung ist oft 0 (1). Zum Beispiel ist der Schlüsselraum für DES 2 ^ 56, so dass das Entschlüsseln einer Nachricht eine zeitlich konstante Operation ist. Es ist nur so, dass Sie einen Faktor von 2 ^ 56 haben, also ist es eine wirklich große Konstante.

Zachary K
quelle
Ist die Entschlüsselung einer Nachricht nicht O ( n ), wobei n proportional zur Größe der Nachricht ist? Solange Sie den richtigen Schlüssel haben, wird die Größe des Schlüssels nicht einmal berücksichtigt. Einige Algorithmen haben nur minimale oder gar keine Prozesse zum Einrichten / Erweitern von Schlüsseln (DES, RSA - Beachten Sie, dass das Generieren von Schlüsseln zwar immer noch eine komplexe Aufgabe ist, aber nichts mit dem Erweitern von Schlüsseln zu tun hat Sobald dies erledigt ist, ist die Zeit für die eigentliche Arbeit proportional zur Größe der Nachricht, daher O (n).
ein Lebenslauf vom
Sie meinen wahrscheinlich eher Kryptoanalyse als Entschlüsselung?
linksum den
3
Nun ja, es gibt eine beliebige Anzahl von Dingen, die Sie als konstant annehmen und einen Algorithmus als O (1) deklarieren können. [Beim Sortieren wird implizit davon ausgegangen, dass die Elemente eine konstante Zeit benötigen, um beispielsweise oder eine beliebige Mathematik mit Nicht-Bignum-Zahlen zu vergleichen]
Random832,
1

Verschiedene Implementierungen von Sets kommen mir in den Sinn. Eine der naivsten ist die Implementierung über einen Vektor, was bedeutet remove, dass auch containsund deshalb auch addalle O (N) nehmen.
Eine Alternative ist die Implementierung über einen allgemeinen Hash, der Eingabehashes auf Eingabewerte abbildet. Eine solche Mengenimplementierung führt mit O (1) für add, containsund remove.

Wenn wir annehmen, dass N ungefähr 10 ist, ist die erste Implementierung wahrscheinlich schneller. Um ein Element zu finden, müssen lediglich 10 Werte mit einem verglichen werden.
Die andere Implementierung muss alle Arten von cleveren Transformationen starten, die viel teurer sein können, als 10 Vergleiche anzustellen. Bei all dem Overhead kann es sogar zu Cache-Fehlern kommen, und dann spielt es keine Rolle, wie schnell Ihre Lösung theoretisch ist.

Dies bedeutet nicht, dass die schlechteste Implementierung, die Sie sich vorstellen können, eine anständige übertrifft, wenn N klein genug ist. Für ausreichend kleine N bedeutet dies einfach, dass eine naive Implementierung mit geringem Platzbedarf und Overhead tatsächlich weniger Anweisungen erfordern und weniger Cache-Fehler verursachen kann als eine Implementierung, bei der die Skalierbarkeit an erster Stelle steht und die daher schneller ist.

Man kann nicht wirklich wissen, wie schnell etwas in einem realen Szenario ist, bis man es in eines einsetzt und es einfach misst. Oft sind die Ergebnisse überraschend (zumindest für mich).

back2dos
quelle
1

Ja, für entsprechend kleines N. Es wird immer ein N geben, über dem Sie immer die Reihenfolge O (1) <O (lg N) <O (N) <O (N log N) <O (N c haben ) <O (c ^ N) (wobei O (1) <O (lg N) bedeutet, dass bei einem O (1) -Algorithmus weniger Operationen ausgeführt werden, wenn N geeignet groß ist und c eine feste Konstante ist, die größer als 1 ist ).

Angenommen, ein bestimmter O (1) -Algorithmus benötigt genau f (N) = 10 ^ 100 (a googol) -Operationen und ein O (N) -Algorithmus benötigt genau g (N) = 2 N + 5 Operationen. Der O (N) -Algorithmus liefert eine höhere Leistung, bis N ungefähr ein Googol ist (tatsächlich, wenn N> (10 ^ 100 - 5) / 2). Wenn Sie also nur damit gerechnet haben, dass N im Bereich von 1000 bis einer Milliarde liegt, haben Sie würde unter Verwendung des O (1) -Algorithmus eine größere Strafe erleiden.

Zum realistischen Vergleich können Sie auch n-stellige Zahlen miteinander multiplizieren. Der Karatsuba-Algorithmus besteht aus höchstens 3 n ^ (lg 3) Operationen (dh ungefähr 0 (n ^ 1,585)), während der Schönhage-Strassen-Algorithmus 0 (N log N log N) ist, was eine schnellere Ordnung darstellt , aber zu zitieren ist Wikipedia:

In der Praxis beginnt der Schönhage-Strassen-Algorithmus, ältere Methoden wie Karatsuba und die Toom-Cook-Multiplikation für Zahlen jenseits von 2 ^ 2 ^ 15 bis 2 ^ 2 ^ 17 (10.000 bis 40.000 Dezimalstellen) zu übertreffen. [4] [5] [6 ]

Wenn Sie also 500-stellige Zahlen miteinander multiplizieren, ist es nicht sinnvoll, den Algorithmus zu verwenden, der durch große O-Argumente "schneller" ist.

EDIT: Sie können f (N) im Vergleich zu g (N) bestimmen, indem Sie die Grenze N-> unendlich von f (N) / g (N) nehmen. Wenn die Grenze 0 ist, dann ist f (N) <g (N), wenn die Grenze unendlich ist, dann ist f (N)> g (N), und wenn die Grenze eine andere Konstante ist, dann sind f (N) ~ g (N) in Bezug auf die große O-Notation.

Dr. Jimbob
quelle
1

Die Simplex-Methode für die lineare Programmierung kann im schlimmsten Fall exponentiell sein, während relativ neue Algorithmen für innere Punkte polynomisch sein können.

In der Praxis tritt der exponentiell schlechteste Fall für die Simplex-Methode jedoch nicht auf - die Simplex-Methode ist schnell und zuverlässig, während frühe Algorithmen für innere Punkte viel zu langsam waren, um wettbewerbsfähig zu sein. (Es gibt jetzt modernere innere Punkt - Algorithmen , die sind wettbewerbsfähig - aber die Simplex - Methode ist auch ...)

kommendes Gewitter
quelle
0

Ukkonens Algorithmus zum Erstellen von Suffixen lautet O (n log n). Es hat den Vorteil, dass es "online" ist, dh Sie können schrittweise mehr Text anhängen.

In letzter Zeit haben andere komplexere Algorithmen behauptet, in der Praxis schneller zu sein, hauptsächlich weil ihr Speicherzugriff eine höhere Lokalität aufweist, wodurch die Prozessor-Cache-Auslastung verbessert und CPU-Pipeline-Stillstände vermieden werden. Siehe z. B. diese Umfrage , in der behauptet wird, dass 70-80% der Verarbeitungszeit für das Warten auf Speicher aufgewendet wird, und dieses Papier , das den "wotd" -Algorithmus beschreibt.

Suffix-Versuche sind wichtig in der Genetik (für die Zuordnung von Gensequenzen) und, etwas weniger wichtig, bei der Implementierung von Scrabble-Wörterbüchern.

Ed Staub
quelle
0

Es gibt immer den schnellsten und kürzesten Algorithmus für jedes genau definierte Problem . Es ist jedoch nur rein theoretisch der (asymptotisch) schnellste Algorithmus.

Bei gegebener Beschreibung eines Problems P und einer Instanz für dieses Problem I werden alle möglichen Algorithmen A und Beweise Pr aufgelistet , wobei für jedes dieser Paare geprüft wird, ob Pr ein gültiger Beweis dafür ist, dass A der asymptotisch schnellste Algorithmus für P ist . Wenn es einen solchen Beweis findet, führt es A auf I aus .

Die Suche nach diesem problemfreien Paar hat die Komplexität O (1) (für ein festes Problem P ), sodass Sie immer den asymptotisch schnellsten Algorithmus für das Problem verwenden. Da diese Konstante in fast allen Fällen so unbeschreiblich groß ist, ist diese Methode in der Praxis völlig unbrauchbar.

Alex ten Brink
quelle
0

Viele Sprachen / Frameworks verwenden einen naiven Mustervergleich, um Zeichenfolgen anstelle von KMP abzugleichen . Wir suchen eher nach Streichern wie Tom, New York als nach Ababaababababababababababab.

Lukasz Madon
quelle