Kann mir jemand ein realistisches Beispiel geben, in dem ein O(N*N) Algorithmus schneller ist als ein O(N) Algorithmus für einige N>10 .
EDIT: Ich sehe, dass diese Frage für zu allgemein gehalten wird. Aber ich habe nur eine allgemeine Frage. Es gibt keinen anderen Weg, diese Frage anders zu stellen.
Es könnte sein, dass einige versuchten, einen O (N * N) -Algorithmus schneller zu machen (z. B. durch Einführung einer gewissen Vorkonditionierung der Daten) und am Ende mit etwas wie diesem enden:
O (N):
%Vor%O (N * N):
%Vor%Die große O-Notation ist nur das begrenzende Verhalten für großes N. Der konstante (oder lineare) Teil kann sehr unterschiedlich sein. Zum Beispiel könnte es sein, dass
%Vor%Kann jemand mir ein realistisches Beispiel geben, in dem ein O (N * N) Algorithmus für einige N & gt; 10 schneller ist als ein O (N) Algorithmus.
Die große O-Notation beschreibt nur die asymptotische Leistung eines Algorithmus, wobei N zur positiven Unendlichkeit neigt.
Und vor allem: es beschreibt die theoretische Leistung des Algorithmus - nicht seiner praktischen Umsetzung!
Deshalb werden die Konstanten und die Nebenfunktionen, die sich auf andere Gemeinkosten beziehen, in der großen O-Notation weggelassen. Sie sind für die Form der Hauptfunktion irrelevant (besonders wenn N gegen unendlich geht) - aber sie sind entscheidend für die Analyse der realen Leistung der Implementierung des Algorithmus.
Einfaches Beispiel. Setzen Sie sleep(60) in die Funktion qsort() . Asymptotisch ist der Algorithmus immer noch der gleiche O(N*log(N)) -Algorithmus, weil der konstante 60 Sekunden Schlaf im Vergleich zur Unendlichkeit winzig ist. Aber in der Praxis würde eine solche qsort() -Implementierung bei jeder Bubble-Sort-Implementierung (ohne sleep() ) übertroffen werden, weil nun vor der N*log(N) riesige Konstante steht.
Eingabe ist eine Ganzzahl n.
Erstes Beispiel: Ein Paar kurzer Programme, die die Tatsache verwenden, dass die O-Notation eine obere Grenze ist, also ein Programm, das O (1) ist, ist auch O (n) und O (n ^ 2), usw.
Programm 1:
%Vor%Programm 2:
%Vor%Programm 1 ist O (n) und Programm 2 ist O (n * n) sowie O (n) und O (1) und O (n ^ n ^ n ^ n ^ n).
Aber Programm 2 ist schneller als Programm 1.
Zweites Beispiel: Ein Paar Programme, die die Tatsache verwenden, dass die O-Notation vom Verhalten abhängt, wird als n groß.
Programm 1: wie vorher
Programm 2:
%Vor%Programm 1 ist O (n) und Programm 2 ist O (n * n).
Programm 2 ist jedoch schneller als Programm bis n & gt; = 10 ^ 100.
Als realistisches Beispiel finden Sie meine Antwort auf diese Frage .
Median von N Zahlen können in O (N) Zeit gefunden werden (entweder im schlechtesten Fall oder im Durchschnitt). Ein solcher Algorithmus wird beispielsweise in std::nth_element implementiert.
Für kleine N kann jedoch ein vorgeschlagener Algorithmus mit O (N ^ 2) -Komplexität schneller ausgeführt werden, weil 1) er keine Verzweigungen hat, 2) er sein kann vektorisiert mit SSE. Zumindest für N = 23 Elemente von short type übertrifft es 4-5 mal std::nth_element . Diese spezielle Einstellung hat ihre Anwendung in der Bildverarbeitung.
PS Übrigens verwenden Implementierungen von std::nth_element normalerweise intern die Einfügesortierung, wenn N & lt; = 32 , was auch ein O (N ^ ist 2) Algorithmus.