Gibt es Fälle, in denen Sie O(log n)
Zeitkomplexität der O(1)
Zeitkomplexität vorziehen würden ? Oder O(n)
zu O(log n)
?
Hast du irgendwelche Beispiele?
algorithm
big-o
time-complexity
V. Leymarie
quelle
quelle
O(log n)
Algorithmus einemO(1)
Algorithmus vorziehen , wenn ich den ersteren verstehe, aber nicht den letzteren ...Antworten:
Es kann viele Gründe geben, einen Algorithmus mit einer höheren Komplexität der großen O-Zeit dem niedrigeren vorzuziehen:
10^5
ist aus Sicht von big-O besser als1/10^5 * log(n)
(O(1)
vsO(log(n)
), aber für die meisten vernünftigen wirdn
der erste besser abschneiden. Zum Beispiel ist die beste Komplexität für die Matrixmultiplikation,O(n^2.373)
aber die Konstante ist so hoch, dass keine (meines Wissens) Computerbibliotheken sie verwenden.O(n*log(n))
oder nichtO(n^2)
.O(log log N)
zeitliche Komplexität für das Finden eines Elements bietet, aber es gibt auch einen Binärbaum, der dasselbe in findetO(log n)
. Selbst für große Mengen istn = 10^20
der Unterschied vernachlässigbar.O(n^2)
undO(n^2)
Speicher benötigt . Es könnteO(n^3)
zeitlich undO(1)
räumlich vorzuziehen sein , wenn das n nicht wirklich groß ist. Das Problem ist, dass Sie lange warten können, aber sehr bezweifeln, dass Sie einen RAM finden, der groß genug ist, um ihn mit Ihrem Algorithmus zu verwendenAn einigen Stellen (Sicherheit) kann eine Komplexität erforderlich sein. Niemand möchte einen Hash-Algorithmus haben, der blitzschnell hashen kann (weil andere Leute Sie dann viel schneller brutal erzwingen können).O(n^2)
, schlechter als Quicksort oder Mergesort, aber als Online-Algorithmus kann sie eine Liste von Werten beim Empfang (als Benutzereingabe) effizient sortieren, wobei die meisten anderen Algorithmen nur effizient arbeiten können auf einer vollständigen Liste von Werten.quelle
Es gibt immer die versteckte Konstante, die beim O (log n ) -Algorithmus niedriger sein kann. So kann es in der Praxis schneller für reale Daten arbeiten.
Es gibt auch Platzprobleme (z. B. Laufen auf einem Toaster).
Es gibt auch Bedenken hinsichtlich der Entwicklerzeit - O (log n ) ist möglicherweise 1000-mal einfacher zu implementieren und zu überprüfen.
quelle
lg n
ist so, so, so nahk
für groß,n
dass die meisten Operationen den Unterschied nie bemerken würden.Ich bin überrascht, dass noch niemand speichergebundene Anwendungen erwähnt hat.
Es kann einen Algorithmus geben, der entweder aufgrund seiner Komplexität (dh O (1) < O (log n )) oder weil die Konstante vor der Komplexität kleiner ist (dh 2 n 2 <6 n 2 ) , weniger Gleitkommaoperationen aufweist. . Unabhängig davon bevorzugen Sie möglicherweise immer noch den Algorithmus mit mehr FLOP, wenn der niedrigere FLOP-Algorithmus stärker speichergebunden ist.
Was ich unter "speichergebunden" verstehe, ist, dass Sie häufig auf Daten zugreifen, die sich ständig außerhalb des Cache befinden. Um diese Daten abzurufen, müssen Sie den Speicher aus Ihrem eigentlichen Speicherplatz in Ihren Cache ziehen, bevor Sie Ihre Operation daran ausführen können. Dieser Abrufschritt ist oft sehr langsam - viel langsamer als Ihre Operation selbst.
Wenn Ihr Algorithmus mehr Operationen erfordert (diese Operationen werden jedoch für Daten ausgeführt, die sich bereits im Cache befinden [und daher kein Abrufen erforderlich ist]), führt er Ihren Algorithmus dennoch mit weniger Operationen aus (die bei Out-of ausgeführt werden müssen) -Cache-Daten [und erfordern daher einen Abruf]) in Bezug auf die tatsächliche Wandzeit.
quelle
O(logn)
überO(1)
. Sie können sich sehr leicht eine Situation vorstellenn
, in der die weniger speichergebundene Anwendung trotz aller Möglichkeiten in einer schnelleren Wandzeit ausgeführt wird, selbst bei einer höheren Komplexität.In Kontexten, in denen Datensicherheit ein Problem darstellt, kann ein komplexerer Algorithmus einem weniger komplexen Algorithmus vorzuziehen sein, wenn der komplexere Algorithmus eine bessere Beständigkeit gegen Timing-Angriffe aufweist .
quelle
(n mod 5) + 1
, ist sie immer nochO(1)
, zeigt jedoch Informationen übern
. Ein komplexerer Algorithmus mit einer reibungsloseren Laufzeit kann daher vorzuziehen sein, selbst wenn er asymptotisch (und möglicherweise sogar in der Praxis) langsamer ist.Alistra hat es geschafft, aber keine Beispiele geliefert, also werde ich es tun.
Sie haben eine Liste mit 10.000 UPC-Codes für das, was Ihr Geschäft verkauft. 10-stellige UPC, Ganzzahl für Preis (Preis in Cent) und 30 Zeichen Beschreibung für die Quittung.
O (log N) Ansatz: Sie haben eine sortierte Liste. 44 Bytes bei ASCII, 84 bei Unicode. Alternativ können Sie die UPC als int64 behandeln und Sie erhalten 42 und 72 Bytes. 10.000 Datensätze - im höchsten Fall sehen Sie etwas weniger als ein Megabyte Speicherplatz.
O (1) -Ansatz: Speichern Sie die UPC nicht, sondern verwenden Sie sie als Eintrag in das Array. Im niedrigsten Fall sehen Sie fast ein Drittel eines Terabytes Speicherplatz.
Welchen Ansatz Sie verwenden, hängt von Ihrer Hardware ab. Bei den meisten vernünftigen modernen Konfigurationen verwenden Sie den Log N-Ansatz. Ich kann mir vorstellen, dass der zweite Ansatz die richtige Antwort ist, wenn Sie aus irgendeinem Grund in einer Umgebung arbeiten, in der der Arbeitsspeicher kritisch kurz ist, Sie aber über ausreichend Massenspeicher verfügen. Ein Drittel eines Terabytes auf einer Festplatte ist keine große Sache. Es ist etwas wert, Ihre Daten in einer Sonde der Festplatte zu speichern. Der einfache binäre Ansatz dauert durchschnittlich 13. (Beachten Sie jedoch, dass Sie durch Clustering Ihrer Schlüssel diese auf garantierte 3 Lesevorgänge reduzieren können und in der Praxis den ersten zwischenspeichern würden.)
quelle
malloc(search_space_size)
und Abonnieren der zurückgegebenen Daten ist so einfach wie möglich.Betrachten Sie einen rot-schwarzen Baum. Es hat Zugriff, Suche, Einfügen und Löschen von
O(log n)
. Vergleichen Sie mit einem Array, auf das zugegriffen werden kann,O(1)
und die restlichen Operationen sindO(n)
.Bei einer Anwendung, bei der wir häufiger einfügen, löschen oder suchen als wir zugreifen, und nur zwischen diesen beiden Strukturen wählen, würden wir den rot-schwarzen Baum bevorzugen. In diesem Fall könnte man sagen, wir bevorzugen die umständlichere
O(log n)
Zugriffszeit des rot-schwarzen Baums .Warum? Weil der Zugang nicht unser vorrangiges Anliegen ist. Wir machen einen Kompromiss: Die Leistung unserer Anwendung wird stärker von anderen Faktoren als diesem beeinflusst. Wir lassen zu, dass dieser spezielle Algorithmus unter der Leistung leidet, da wir durch die Optimierung anderer Algorithmen große Gewinne erzielen.
Die Antwort auf Ihre Frage lautet also einfach: Wenn die Wachstumsrate des Algorithmus nicht das ist, was wir optimieren möchten , wenn wir etwas anderes optimieren möchten. Alle anderen Antworten sind Sonderfälle. Manchmal optimieren wir die Laufzeit anderer Operationen. Manchmal optimieren wir das Gedächtnis. Manchmal optimieren wir für die Sicherheit. Manchmal optimieren wir die Wartbarkeit. Manchmal optimieren wir die Entwicklungszeit. Selbst die übergeordnete Konstante, die niedrig genug ist, um eine Rolle zu spielen, optimiert die Laufzeit, wenn Sie wissen, dass die Wachstumsrate des Algorithmus nicht den größten Einfluss auf die Laufzeit hat. (Wenn Ihr Datensatz außerhalb dieses Bereichs liegt, würden Sie die Wachstumsrate des Algorithmus optimieren, da er letztendlich die Konstante dominieren würde.) Alles hat Kosten, und in vielen Fällen tauschen wir die Kosten einer höheren Wachstumsrate gegen die Algorithmus, um etwas anderes zu optimieren.
quelle
O(log n)
"rot-schwarzer Baum" deklarieren ? Das Einfügen von5
in Position 2 des Arrays[1, 2, 1, 4]
führt zu[1, 2, 5, 1 4]
(das Element4
wird von 3 auf 4 aktualisiert). Wie können Sie dieses Verhalten inO(log n)
den "rot-schwarzen Baum" integrieren, den Sie als "sortierte Liste" bezeichnen?Ja.
In einem realen Fall haben wir einige Tests durchgeführt, um Tabellensuchen mit kurzen und langen Zeichenfolgenschlüsseln durchzuführen.
Wir haben a
std::map
, astd::unordered_map
mit einem Hash verwendet, der höchstens zehnmal über die Länge der Zeichenfolge abtastet (unsere Schlüssel sind in der Regel führerisch, das ist also anständig), und einen Hash, der jedes Zeichen abtastet (theoretisch reduzierte Kollisionen). Ein unsortierter Vektor, in dem wir==
vergleichen, und (wenn ich mich richtig erinnere) ein unsortierter Vektor, in dem wir auch einen Hash speichern. Vergleichen Sie zuerst den Hash und dann die Zeichen.Diese Algorithmen reichen von
O(1)
(unordered_map) bisO(n)
(lineare Suche).Bei N mit bescheidener Größe schlägt O (n) häufig O (1). Wir vermuten, dass dies daran liegt, dass die knotenbasierten Container von unserem Computer mehr Speicherplatz benötigen, während die linearen Container dies nicht taten.
O(lg n)
existiert zwischen den beiden. Ich erinnere mich nicht, wie es war.Der Leistungsunterschied war nicht so groß, und bei größeren Datenmengen schnitt der Hash-basierte viel besser ab. Also blieben wir bei der Hash-basierten ungeordneten Karte.
In der Praxis für einen vernünftigen Größe n,
O(lg n)
istO(1)
. Wenn Ihr Computer nur Platz für 4 Milliarden Einträge in Ihrer Tabelle hat,O(lg n)
wird dies oben durch begrenzt32
. (lg (2 ^ 32) = 32) (in der Informatik ist lg eine Abkürzung für log based 2).In der Praxis sind lg (n) -Algorithmen langsamer als O (1) -Algorithmen, nicht wegen des logarithmischen Wachstumsfaktors, sondern weil der lg (n) -Anteil normalerweise bedeutet, dass der Algorithmus einen bestimmten Grad an Komplexität aufweist und diese Komplexität a hinzufügt größerer konstanter Faktor als irgendein "Wachstum" aus dem lg (n) -Term.
Komplexe O (1) -Algorithmen (wie Hash-Mapping) können jedoch leicht einen ähnlichen oder größeren konstanten Faktor aufweisen.
quelle
Die Möglichkeit, einen Algorithmus parallel auszuführen.
Ich weiß nicht, ob es ein Beispiel für die Klassen gibt,
O(log n)
undO(1)
für einige Probleme wählen Sie einen Algorithmus mit einer Klasse mit höherer Komplexität, wenn der Algorithmus einfacher parallel auszuführen ist.Einige Algorithmen können nicht parallelisiert werden, haben jedoch eine so geringe Komplexitätsklasse. Stellen Sie sich einen anderen Algorithmus vor, der das gleiche Ergebnis erzielt und leicht parallelisiert werden kann, jedoch eine höhere Komplexitätsklasse aufweist. Bei der Ausführung auf einem Computer ist der zweite Algorithmus langsamer. Bei der Ausführung auf mehreren Computern wird die tatsächliche Ausführungszeit jedoch immer kürzer, während der erste Algorithmus nicht beschleunigt werden kann.
quelle
Angenommen, Sie implementieren eine Blacklist auf einem eingebetteten System, auf dem möglicherweise Zahlen zwischen 0 und 1.000.000 auf die Blacklist gesetzt werden. Damit haben Sie zwei Möglichkeiten:
Der Zugriff auf das Bitset garantiert einen konstanten Zugriff. In Bezug auf die zeitliche Komplexität ist es optimal. Sowohl aus theoretischer als auch aus praktischer Sicht (es ist O (1) mit einem extrem niedrigen konstanten Overhead).
Dennoch möchten Sie vielleicht die zweite Lösung bevorzugen. Insbesondere, wenn Sie erwarten, dass die Anzahl der Ganzzahlen auf der schwarzen Liste sehr gering ist, da sie speichereffizienter sind.
Und selbst wenn Sie nicht für ein eingebettetes System entwickeln, in dem der Speicher knapp ist, kann ich die willkürliche Grenze von 1.000.000 auf 1.000.000.000.000 erhöhen und das gleiche Argument vorbringen. Dann würde das Bitset ungefähr 125 G Speicher benötigen. Eine garantierte Worst-Case-Komplexität von O (1) kann Ihren Chef möglicherweise nicht davon überzeugen, Ihnen einen so leistungsstarken Server zur Verfügung zu stellen.
Hier würde ich eine binäre Suche (O (log n)) oder einen binären Baum (O (log n)) dem O (1) -Bitset vorziehen. Und wahrscheinlich wird eine Hash-Tabelle mit der Worst-Case-Komplexität von O (n) in der Praxis alle schlagen.
quelle
Meine Antwort hier Die schnelle, zufällig gewichtete Auswahl über alle Zeilen einer stochastischen Matrix ist ein Beispiel, bei dem ein Algorithmus mit der Komplexität O (m) schneller ist als einer mit der Komplexität O (log (m)), wenn er
m
nicht zu groß ist.quelle
Die Leute haben Ihre genaue Frage bereits beantwortet, daher werde ich eine etwas andere Frage ansprechen, an die die Leute vielleicht tatsächlich denken, wenn sie hierher kommen.
Viele der "O (1) -Zeit" -Algorithmen und Datenstrukturen benötigen tatsächlich nur die erwartete O (1) -Zeit, was bedeutet, dass ihre durchschnittliche Laufzeit O (1) beträgt, möglicherweise nur unter bestimmten Annahmen.
Häufige Beispiele: Hashtabellen, Erweiterung von "Array-Listen" (auch bekannt als dynamisch dimensionierte Arrays / Vektoren).
In solchen Szenarien bevorzugen Sie möglicherweise die Verwendung von Datenstrukturen oder Algorithmen, deren Zeit garantiert absolut logarithmisch begrenzt ist, obwohl sie im Durchschnitt schlechter abschneiden.
Ein Beispiel könnte daher ein ausgeglichener binärer Suchbaum sein, dessen Laufzeit im Durchschnitt schlechter, im schlimmsten Fall jedoch besser ist.
quelle
Eine allgemeine Frage ist , ob es Situationen , in denen man einen bevorzugen
O(f(n))
Algorithmus zu einemO(g(n))
Algorithmus , obwohlg(n) << f(n)
alsn
gegen Unendlich. Wie andere bereits erwähnt haben, lautet die Antwort in dem Fall, in demf(n) = log(n)
undg(n) = 1
. Es ist manchmal ja sogar in dem Fall, dassf(n)
es polynomisch, aberg(n)
exponentiell ist. Ein berühmtes und wichtiges Beispiel ist der Simplex-Algorithmus zur Lösung linearer Programmierprobleme. In den 1970er Jahren wurde es gezeigtO(2^n)
. Somit ist sein Worst-Case-Verhalten nicht realisierbar. Aber - sein durchschnittliches Fallverhalten ist extrem gut, selbst bei praktischen Problemen mit Zehntausenden von Variablen und Einschränkungen. In den 1980er Jahren wurden polynomielle Zeitalgorithmen (wie zKarmarkars Interieur-Punkt-Algorithmus) für die lineare Programmierung wurden entdeckt, aber 30 Jahre später scheint der Simplex-Algorithmus immer noch der Algorithmus der Wahl zu sein (mit Ausnahme bestimmter sehr großer Probleme). Dies liegt an dem offensichtlichen Grund, dass das Verhalten im Durchschnitt häufig wichtiger ist als das Verhalten im schlimmsten Fall, aber auch an einem subtileren Grund, dass der Simplex-Algorithmus in gewissem Sinne informativer ist (z. B. sind Sensitivitätsinformationen leichter zu extrahieren).quelle
Um meine 2 Cent einzulegen:
Manchmal wird ein Algorithmus mit schlechterer Komplexität anstelle eines besseren Algorithmus ausgewählt, wenn der Algorithmus in einer bestimmten Hardwareumgebung ausgeführt wird. Angenommen, unser O (1) -Algorithmus greift nicht sequentiell auf jedes Element eines sehr großen Arrays mit fester Größe zu, um unser Problem zu lösen. Legen Sie das Array dann auf eine mechanische Festplatte oder ein Magnetband.
In diesem Fall wird der O (logn) -Algorithmus (vorausgesetzt, er greift nacheinander auf die Festplatte zu) günstiger.
quelle
Es gibt einen guten Anwendungsfall für die Verwendung eines O (log (n)) - Algorithmus anstelle eines O (1) -Algorithmus, den die zahlreichen anderen Antworten ignoriert haben: Unveränderlichkeit. Hash-Maps haben O (1) -Puts und Get-Werte unter der Annahme einer guten Verteilung der Hash-Werte, erfordern jedoch einen veränderlichen Status. Unveränderliche Baumkarten haben O (log (n)) Puts und Get, was asymptotisch langsamer ist. Unveränderlichkeit kann jedoch wertvoll genug sein, um eine schlechtere Leistung auszugleichen. Wenn mehrere Versionen der Karte beibehalten werden müssen, können Sie durch Unveränderlichkeit vermeiden, dass Sie die Karte kopieren müssen, die O (n) ist, und können sich daher verbessern Performance.
quelle
Einfach: Weil der Koeffizient - die Kosten für Einrichtung, Speicherung und Ausführungszeit dieses Schritts - bei einem kleineren Big-O-Problem sehr viel größer sein kann als bei einem größeren. Big-O ist nur ein Maß für die Skalierbarkeit der Algorithmen .
Betrachten Sie das folgende Beispiel aus dem Hacker-Wörterbuch und schlagen Sie einen Sortieralgorithmus vor, der auf der Interpretation der Quantenmechanik in mehreren Welten beruht :
(Quelle: http://catb.org/~esr/jargon/html/B/bogo-sort.html )
Beachten Sie, dass das Big-O dieses Algorithmus ist
O(n)
, das jeden bisher bekannten Sortieralgorithmus für generische Elemente übertrifft. Der Koeffizient des linearen Schritts ist ebenfalls sehr niedrig (da es sich nur um einen Vergleich handelt, nicht um einen Austausch, der linear durchgeführt wird). Ein ähnlicher Algorithmus könnte tatsächlich verwendet werden, um jedes Problem sowohl im NP als auch im Co-NP zu lösen in Polynomzeit , da jede mögliche Lösung (oder jeder mögliche Beweis, dass es keine Lösung gibt) unter Verwendung des Quantenprozesses erzeugt und dann in verifiziert werden kann Polynomzeit.In den meisten Fällen möchten wir jedoch wahrscheinlich nicht das Risiko eingehen, dass mehrere Welten nicht korrekt sind, ganz zu schweigen davon, dass der Vorgang der Implementierung von Schritt 2 immer noch "als Übung für den Leser" bleibt.
quelle
Zu jedem Zeitpunkt, an dem n begrenzt ist und der konstante Multiplikator des O (1) -Algorithmus höher ist als der an log (n) gebundene. Das Speichern von Werten in einem Hashset ist beispielsweise O (1), erfordert jedoch möglicherweise eine teure Berechnung einer Hashfunktion. Wenn die Datenelemente trivial verglichen werden können (in Bezug auf eine bestimmte Reihenfolge) und die Grenze für n so ist, dass log n erheblich kleiner ist als die Hash-Berechnung für ein Element, kann das Speichern in einem ausgeglichenen Binärbaum schneller sein als das Speichern in ein Hashset.
quelle
In einer Echtzeitsituation, in der Sie eine feste Obergrenze benötigen, würden Sie z. B. einen Heapsort im Gegensatz zu einem Quicksort auswählen, da das durchschnittliche Verhalten von Heapsort auch das Worst-Case-Verhalten ist.
quelle
Ein praktisches Beispiel wären Hash-Indizes im Vergleich zu B-Tree-Indizes in der Postgres-Datenbank.
Hash-Indizes bilden einen Hash-Tabellenindex für den Zugriff auf die Daten auf der Festplatte, während btree, wie der Name schon sagt, eine Btree-Datenstruktur verwendet.
In der Big-O-Zeit sind dies O (1) gegen O (logN).
Von Hash-Indizes wird derzeit in Postgres abgeraten, da in einer realen Situation, insbesondere in Datenbanksystemen, das Erreichen von Hashing ohne Kollision sehr schwierig ist (was zu einer O (N) Worst-Case-Komplexität führen kann) und aus diesem Grund noch schwieriger zu erstellen ist Sie sind absturzsicher (als Write-Ahead-Protokollierung bezeichnet - WAL in Postgres).
Dieser Kompromiss wird in dieser Situation gemacht, da O (logN) für Indizes gut genug ist und die Implementierung von O (1) ziemlich schwierig ist und der Zeitunterschied nicht wirklich wichtig wäre.
quelle
Wann
n
ist klein undO(1)
ist ständig langsam.quelle
oder
quelle
quelle
Dies ist häufig bei Sicherheitsanwendungen der Fall, bei denen wir Probleme entwerfen möchten, deren Algorithmen absichtlich langsam sind, um zu verhindern, dass jemand zu schnell eine Antwort auf ein Problem erhält.
Hier sind ein paar Beispiele aus meinem Kopf.
O(2^n)
Zeit geknackt werden, in dern
die Bitlänge des Schlüssels liegt (dies ist Brute Force).An anderer Stelle in CS ist die schnelle Sortierung
O(n^2)
im schlimmsten Fall, im allgemeinen Fall jedochO(n*log(n))
. Aus diesem Grund ist die "Big O" -Analyse manchmal nicht das einzige, was Sie bei der Analyse der Algorithmuseffizienz interessiert.quelle