Gibt es Fälle, in denen Sie einen Algorithmus mit höherer Big-O-Zeitkomplexität dem niedrigeren vorziehen würden?

242

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?

V. Leymarie
quelle
67
Ich würde einen O(log n)Algorithmus einem O(1)Algorithmus vorziehen , wenn ich den ersteren verstehe, aber nicht den letzteren ...
Codor
14
Es gibt Unmengen unpraktischer Datenstrukturen mit O (1) -Operationen aus der theoretischen Informatik. Ein Beispiel wäre select () für Bitvektoren, die in o (n) zusätzlichem Speicherplatz und O (1) pro Operation unter Verwendung von 5 Indirektionsebenen unterstützt werden können. Eine einfache binäre Suche in Kombination mit O (1) rank () erweist sich in der Praxis als schneller, so der Autor der Succinct Data Structure Library
Niklas B.
17
Eine geringere asymptotische Komplexität garantiert keine schnelleren Laufzeiten. Forschungsmatrixmultiplikation für ein konkretes Beispiel.
Connor Clark
54
Außerdem ... kann jeder Algorithmus bei einer ausreichend großen Tabellensuche in O (1) konvertiert werden;)
Connor Clark
19
@Hoten - Vorausgesetzt, die Tabellensuche ist O (1), was für die Größe der Tabellen, über die Sie sprechen, überhaupt nicht gegeben ist! :)
Jander

Antworten:

267

Es kann viele Gründe geben, einen Algorithmus mit einer höheren Komplexität der großen O-Zeit dem niedrigeren vorzuziehen:

  • In den meisten Fällen ist eine geringere Big-O-Komplexität schwieriger zu erreichen und erfordert eine qualifizierte Implementierung, viel Wissen und viele Tests.
  • big-O verbirgt die Details einer Konstanten : Der Algorithmus, der in funktioniert, 10^5ist aus Sicht von big-O besser als 1/10^5 * log(n)( O(1)vs O(log(n)), aber für die meisten vernünftigen wird nder 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.
  • big-O macht Sinn, wenn Sie über etwas Großes rechnen. Wenn Sie ein Array mit drei Zahlen sortieren müssen, spielt es keine Rolle, ob Sie einen Algorithmus verwenden O(n*log(n))oder nicht O(n^2).
  • manchmal kann der Vorteil der zeitlichen Komplexität in Kleinbuchstaben wirklich vernachlässigbar sein. Zum Beispiel gibt es einen Datenstruktur-Tangobaum, der eine O(log log N)zeitliche Komplexität für das Finden eines Elements bietet, aber es gibt auch einen Binärbaum, der dasselbe in findet O(log n). Selbst für große Mengen ist n = 10^20der Unterschied vernachlässigbar.
  • Zeitkomplexität ist nicht alles. Stellen Sie sich einen Algorithmus vor, der ausgeführt wird O(n^2)und O(n^2)Speicher benötigt . Es könnte O(n^3)zeitlich und O(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 verwenden
  • Parallelisierung ist ein gutes Merkmal in unserer verteilten Welt. Es gibt Algorithmen, die leicht parallelisierbar sind, und es gibt einige, die überhaupt nicht parallelisieren. Manchmal ist es sinnvoll, einen Algorithmus auf 1000 Standardmaschinen mit einer höheren Komplexität auszuführen als auf einer Maschine mit einer etwas besseren Komplexität.
  • An 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).
  • Dies hängt zwar nicht mit dem Wechsel der Komplexität zusammen, aber einige der Sicherheitsfunktionen sollten so geschrieben sein, dass ein Timing-Angriff verhindert wird . Sie bleiben meistens in derselben Komplexitätsklasse, werden jedoch so modifiziert, dass es immer schlimmer ist, etwas zu tun. Ein Beispiel ist der Vergleich, dass Zeichenfolgen gleich sind. In den meisten Anwendungen ist es sinnvoll, schnell zu brechen, wenn die ersten Bytes unterschiedlich sind. In Bezug auf die Sicherheit warten Sie jedoch bis zum Ende, um die schlechten Nachrichten zu verbreiten.
  • Jemand hat den Algorithmus mit geringerer Komplexität patentiert, und es ist für ein Unternehmen wirtschaftlicher, eine höhere Komplexität zu verwenden, als Geld zu zahlen.
  • Einige Algorithmen passen sich gut an bestimmte Situationen an. Die Einfügungssortierung hat beispielsweise eine durchschnittliche Zeitkomplexität von 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.
Salvador Dali
quelle
6
Außerdem habe ich einige Male gesehen, dass sich die Leute auf das große O ihres zentralen Algorithmus konzentrierten, aber die Einrichtungskosten ignorierten. Das Erstellen einer Hash-Tabelle kann beispielsweise teurer sein als das lineare Durchlaufen eines Arrays, wenn Sie dies nicht immer wieder tun müssen. Aufgrund der Art und Weise, wie moderne CPUs aufgebaut sind, kann sogar so etwas wie die binäre Suche auf sortierten Arrays genauso schnell sein wie eine lineare Suche - Profilerstellung ist eine Notwendigkeit.
Luaan
@Luaan "Aufgrund der Art und Weise, wie moderne CPUs aufgebaut sind, kann sogar die binäre Suche auf sortierten Arrays genauso schnell sein wie eine lineare Suche - Profilerstellung ist eine Notwendigkeit." Interessant! Können Sie erklären, wie die binäre Suche und die lineare Suche auf einer modernen CPU dieselbe Zeit in Anspruch nehmen können?
DJG
3
@Luaan - Egal, ich fand dies: schani.wordpress.com/2010/04/30/linear-vs-binary-search
DJG
2
@ DenisdeBernardy: Nein, eigentlich nicht. Sie könnten Algorithmen in P sein. Und selbst wenn dies nicht unter vernünftigen Definitionen dessen, was es bedeutet, zu parallelisieren, wäre, würde dies auch nicht P! = NP bedeuten. Denken Sie auch daran, dass die Suche im Raum möglicher Läufe einer nicht deterministischen Turingmaschine ziemlich parallelisierbar ist.
Einpoklum
228

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.

Alistra
quelle
Nett, danke. Ich dachte, es könnte sich auch lohnen, einen O (logn) -Algorithmus in Betracht zu ziehen, um die Programmstabilität sicherzustellen (z. B. in selbstausgeglichenen Binärbäumen)
V.Leymarie
16
Ein Beispiel, das ich mir vorstellen kann: Für ein kleines sortiertes Array wäre es für den Programmierer einfacher und kompakter, eine binäre Suchfunktion zu implementieren, als eine vollständige Hash-Map-Implementierung zu schreiben und sie stattdessen zu verwenden.
Oberst
5
Ein Beispiel für Komplexität: Das Finden des Medians einer unsortierten Liste ist in O (n * log n) einfach, in O (n) jedoch schwierig.
Paul Draper
1
-1, lege keine Protokolle in deinen Toaster ... Scherz beiseite, das ist genau richtig. lg nist so, so, so nah kfür groß, ndass die meisten Operationen den Unterschied nie bemerken würden.
CorsiKa
3
Es gibt auch die Tatsache, dass die algorithmischen Komplexitäten, mit denen die meisten Menschen vertraut sind, Cache-Effekte nicht berücksichtigen. Nach etwas in einem Binärbaum zu suchen ist laut den meisten Menschen O (log2 (n)), aber in Wirklichkeit ist es viel schlimmer, weil Binärbäume eine schlechte Lokalität haben.
Doval
57

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.

NoseKnowsAll
quelle
1
Alistra ging indirekt darauf ein, als er über "Weltraumprobleme" sprach
Zach Saucier
2
Eine große Anzahl von Cache-Fehlern multipliziert die endgültige Ausführung nur mit einem konstanten Wert (der bei 4-Kern-3,2-GHz-CPU mit 1,6-GHz-RAM nicht größer als 8 ist, normalerweise ist er viel niedriger), sodass er als feste Konstante im großen Bereich gezählt wird -O Notation. Daher verschiebt der Cache nur die Schwelle von n, wenn diese O (n) -Lösung langsamer als die O (1) -Lösung wird.
Marian Spanik
1
@MarianSpanik Du bist natürlich richtig. Aber diese Frage gestellt für eine Situation , wo wir lieber O(logn)über O(1). Sie können sich sehr leicht eine Situation vorstellen n, in der die weniger speichergebundene Anwendung trotz aller Möglichkeiten in einer schnelleren Wandzeit ausgeführt wird, selbst bei einer höheren Komplexität.
NoseKnowsAll
@MarianSpanik ist kein Cache-Fehler bis zu 300 Taktzyklen? Woher kommt die 8?
Hoffentlich
43

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 .

Kevin K.
quelle
6
Während das, was Sie gesagt haben, wahr ist, ist in diesem Fall ein in O (1) ausgeführter Algorithmus per Definition für Timing-Angriffe unverwundbar.
Justin Lessard
17
@JustinLessard: O (1) zu sein bedeutet, dass es eine Eingabegröße gibt, nach der die Laufzeit des Algorithmus durch eine Konstante begrenzt wird. Was unterhalb dieser Schwelle passiert, ist unbekannt. Außerdem kann der Schwellenwert für eine reale Verwendung des Algorithmus möglicherweise nicht einmal erreicht werden. Der Algorithmus kann linear sein und somit beispielsweise Informationen über die Länge der Eingabe verlieren.
Jörg W Mittag
12
Die Laufzeit kann auch auf unterschiedliche Weise schwanken, während sie noch begrenzt ist. Wenn die Laufzeit proportional zu ist (n mod 5) + 1, ist sie immer noch O(1), zeigt jedoch Informationen über n. Ein komplexerer Algorithmus mit einer reibungsloseren Laufzeit kann daher vorzuziehen sein, selbst wenn er asymptotisch (und möglicherweise sogar in der Praxis) langsamer ist.
Christian Semrau
Dies ist im Grunde der Grund, warum bcrypt als gut angesehen wird. es macht die Dinge langsamer
David sagt Reinstate Monica
@ DavidGrinberg Das ist der Grund, warum bcrypt verwendet wird und passt zu der Frage. Dies hat jedoch nichts mit dieser Antwort zu tun, in der es um Timing-Angriffe geht.
Christian Semrau
37

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.)

Loren Pechtel
quelle
2
Ich bin hier etwas verwirrt. Sprechen Sie über das Erstellen eines Arrays mit 10 Milliarden Einträgen (von denen die meisten undefiniert sind) und das Behandeln der UPC als Index für dieses Array?
David Z
7
@ DavidZ Ja. Wenn Sie ein Array mit geringer Dichte verwenden, erhalten Sie möglicherweise nicht O (1), es wird jedoch nur 1 MB Speicher verwendet. Wenn Sie ein tatsächliches Array verwenden, ist Ihnen der O (1) -Zugriff garantiert, es wird jedoch 1/3 TB Speicher verwendet.
Navin
Auf einem modernen System wird 1/3 TB Adressraum benötigt, aber das bedeutet nicht, dass es dem viel zugewiesenen Sicherungsspeicher nahe kommt. Die meisten modernen Betriebssysteme schreiben erst dann Speicher für Zuweisungen fest, wenn dies erforderlich ist. Dabei verstecken Sie im Wesentlichen eine assoziative Suchstruktur für Ihre Daten im virtuellen Speichersystem des Betriebssystems / der Hardware.
Phil Miller
@ Novelocrat Stimmt, aber wenn Sie es mit RAM-Geschwindigkeit tun, spielt die Suchzeit keine Rolle, kein Grund, 40 MB anstelle von 1 MB zu verwenden. Die Array-Version ist nur dann sinnvoll, wenn der Speicherzugriff teuer ist - Sie gehen auf die Festplatte.
Loren Pechtel
1
Oder wenn dies kein leistungskritischer Vorgang ist und die Entwicklerzeit teuer ist - das Sagen malloc(search_space_size)und Abonnieren der zurückgegebenen Daten ist so einfach wie möglich.
Phil Miller
36

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 sind O(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.

jpmc26
quelle
Sie sind sich nicht sicher, wie Operationen, mit denen Sie ein Array mit O (1) -Suche verwenden und O (n) aktualisieren können, einem rot-schwarzen Baum entsprechen, über den die Leute früher nachgedacht haben (zumindest ich). Die meiste Zeit dachte ich zuerst über die schlüsselbasierte Suche nach rot-schwarzen Bäumen nach. Um jedoch mit dem Array übereinzustimmen, sollte es eine etwas andere Struktur geben, die die Anzahl der Unterknoten in den oberen Knoten beibehält, um eine indexbasierte Suche und einen erneuten Index beim Einfügen zu ermöglichen. Obwohl ich damit einverstanden bin, dass Rot-Schwarz verwendet werden kann, um das Gleichgewicht aufrechtzuerhalten, können Sie einen ausgeglichenen Baum verwenden, wenn Sie Details zu entsprechenden Vorgängen vage sein möchten.
Nur
@ony Ein rot-schwarzer Baum kann verwendet werden, um eine Karten- / Wörterbuchtypstruktur zu definieren, muss es aber nicht sein. Die Knoten können nur Elemente sein, die im Wesentlichen eine sortierte Liste implementieren.
jpmc26
Sortierte Liste und Array, die die Reihenfolge der Elemente definieren, haben unterschiedliche Informationsmengen. Eine basiert auf der Reihenfolge zwischen Elementen und Menge und die andere definiert eine beliebige Reihenfolge, die nicht unbedingt die Reihenfolge zwischen Elementen definiert. Eine andere Sache ist, was ist "Zugriff" und "Suche", die Sie als O(log n)"rot-schwarzer Baum" deklarieren ? Das Einfügen von 5in Position 2 des Arrays [1, 2, 1, 4]führt zu [1, 2, 5, 1 4](das Element 4wird von 3 auf 4 aktualisiert). Wie können Sie dieses Verhalten in O(log n)den "rot-schwarzen Baum" integrieren, den Sie als "sortierte Liste" bezeichnen?
Nur
@ony "Sortierte Liste und Array, die die Reihenfolge der Elemente definieren, haben unterschiedliche Informationsmengen." Ja, und das ist ein Teil dessen, warum sie unterschiedliche Leistungsmerkmale haben. Sie verpassen den Punkt. Das eine ist nicht in allen Situationen ein Ersatz für das andere. Sie optimieren verschiedene Dinge und machen verschiedene Kompromisse . Der Punkt ist, dass Entwickler ständig Entscheidungen über diese Kompromisse treffen.
jpmc26
@ony Zugriff, Suchen, Einfügen und Löschen haben im Zusammenhang mit der Leistung des Algorithmus bestimmte Bedeutungen. Der Zugriff ruft ein Element nach Position ab. Bei der Suche wird ein Element nach Wert gesucht (was nur eine praktische Anwendung als Eindämmungsprüfung für eine Nicht-Kartenstruktur hat). Das Einfügen und Löschen sollte jedoch unkompliziert sein. Ein Beispiel für die Verwendung finden Sie hier .
jpmc26
23

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, a std::unordered_mapmit 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) bis O(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)ist O(1). Wenn Ihr Computer nur Platz für 4 Milliarden Einträge in Ihrer Tabelle hat, O(lg n)wird dies oben durch begrenzt 32. (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.

Yakk - Adam Nevraumont
quelle
21

Die Möglichkeit, einen Algorithmus parallel auszuführen.

Ich weiß nicht, ob es ein Beispiel für die Klassen gibt, O(log n)und O(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.

Simulant
quelle
Aber alles, was Parallelisierung bewirkt, ist, den konstanten Faktor zu reduzieren, über den andere gesprochen haben, oder?
Gengkev
1
Ja, aber ein paralleler Algorithmus kann den konstanten Faktor jedes Mal durch 2 teilen, wenn Sie die Anzahl der ausgeführten Maschinen verdoppeln. Ein anderer Single-Threaded-Algorithmus kann den konstanten Faktor nur einmal auf konstante Weise reduzieren. Mit einem parallelen Algorithmus können Sie also dynamisch auf die Größe von n reagieren und die Ausführungszeit der Wanduhr beschleunigen.
Simulant
15

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:

  1. Verwenden Sie ein Bit-Set von 1.000.000 Bit
  2. Verwenden Sie ein sortiertes Array der Ganzzahlen auf der schwarzen Liste und verwenden Sie eine binäre Suche, um darauf zuzugreifen

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.

Philipp Claßen
quelle
12

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.

user541686
quelle
11

Eine allgemeine Frage ist , ob es Situationen , in denen man einen bevorzugen O(f(n))Algorithmus zu einem O(g(n))Algorithmus , obwohl g(n) << f(n)als ngegen Unendlich. Wie andere bereits erwähnt haben, lautet die Antwort in dem Fall, in dem f(n) = log(n)und g(n) = 1. Es ist manchmal ja sogar in dem Fall, dass f(n)es polynomisch, aber g(n)exponentiell ist. Ein berühmtes und wichtiges Beispiel ist der Simplex-Algorithmus zur Lösung linearer Programmierprobleme. In den 1970er Jahren wurde es gezeigt O(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).

John Coleman
quelle
10

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.

uylmz
quelle
Ich könnte hier hinzufügen, dass auf dem Laufwerk oder Band mit sequentiellem Zugriff der O (1) -Algorithmus stattdessen zu O (n) wird, weshalb die sequentielle Lösung günstiger wird. Viele O (1) -Operationen hängen davon ab, dass das Hinzufügen und die indizierte Suche ein Algorithmus mit konstanter Zeit ist, der sich nicht in einem Raum mit sequentiellem Zugriff befindet.
TheHansinator
9

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.

Stellen Sie Monica wieder her
quelle
9

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 :

  1. Permutieren Sie das Array zufällig mit einem Quantenprozess.
  2. Wenn das Array nicht sortiert ist, zerstören Sie das Universum.
  3. Alle verbleibenden Universen sind jetzt sortiert [einschließlich des Universums, in dem Sie sich befinden].

(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.

Der Hansinator
quelle
7

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.

Dmitry Rubanovich
quelle
6

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.

Marquis von Lorne
quelle
6

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.

Madusudanan
quelle
4

Wann nist klein und O(1)ist ständig langsam.

HoboBen
quelle
3
  1. Wenn die Arbeitseinheit "1" in O (1) relativ zur Arbeitseinheit in O (log n) sehr hoch ist und die erwartete eingestellte Größe klein ist. Zum Beispiel ist es wahrscheinlich langsamer, Dictionary-Hash-Codes zu berechnen, als ein Array zu iterieren, wenn nur zwei oder drei Elemente vorhanden sind.

oder

  1. Wenn der Speicherbedarf oder andere nicht zeitliche Ressourcenanforderungen im O (1) -Algorithmus im Vergleich zum O (log n) -Algorithmus außergewöhnlich groß sind.
Joel Coehoorn
quelle
3
  1. Beim Neugestalten eines Programms wird festgestellt, dass eine Prozedur mit O (1) anstelle von O (lgN) optimiert wird. Wenn dies jedoch nicht der Engpass dieses Programms ist und die O (1) -Alge schwer zu verstehen ist. Dann müssten Sie keinen O (1) -Algorithmus verwenden
  2. wenn O (1) viel Speicher benötigt, den Sie nicht bereitstellen können, während die Zeit von O (lgN) akzeptiert werden kann.
Yanghaogn
quelle
1

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.

  • Das Hashing von Passwörtern wird manchmal willkürlich verlangsamt, um das Erraten von Passwörtern mit Brute-Force zu erschweren. Dieser Beitrag zur Informationssicherheit enthält einen Aufzählungspunkt (und vieles mehr).
  • Bitmünze verwendet ein kontrollierbar langsames Problem, das ein Computernetzwerk lösen muss, um Münzen abzubauen. Dadurch kann die Währung vom kollektiven System zu einem kontrollierten Kurs abgebaut werden.
  • Asymmetrische Chiffren (wie RSA ) dienen dazu, die Entschlüsselung ohne die absichtlich absichtlichen Schlüssel zu verlangsamen, um zu verhindern, dass andere Personen ohne den privaten Schlüssel die Verschlüsselung knacken. Die Algorithmen sind so konzipiert, dass sie hoffentlich in der O(2^n)Zeit geknackt werden, in der ndie 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 jedoch O(n*log(n)). Aus diesem Grund ist die "Big O" -Analyse manchmal nicht das einzige, was Sie bei der Analyse der Algorithmuseffizienz interessiert.

Frank Bryce
quelle