Ich habe mehrmals gehört, dass für ausreichend kleine Werte von n O (n) so betrachtet / behandelt werden kann, als wäre es O (1).

Beispiel :

Die Motivation dafür basiert auf der falschen Vorstellung, dass O (1) immer besser ist als O (lg n), immer besser als O (n). Die asymptotische Reihenfolge einer Operation ist nur relevant, wenn unter realistischen Bedingungen das Problem tatsächlich groß wird. Wenn n klein bleibt, ist jedes Problem O (1)!

Was ist ausreichend klein? 10? 100? 1.000? An welchem ​​Punkt sagen Sie, "wir können das nicht mehr wie eine freie Operation behandeln"? Gibt es eine Faustregel?

Dies scheint domänenspezifisch oder fallspezifisch zu sein, aber gibt es allgemeine Faustregeln, wie man darüber nachdenkt?

Alle Größenordnungen beinhalten ein konstantes , von denen einige tatsächlich sind. Wenn die Anzahl der Elemente groß genug ist, ist diese Konstante irrelevant. Die Frage ist, ob die Anzahl der Elemente klein genug ist, um diese Konstante zu dominieren.$C$

Hier ist eine visuelle Möglichkeit, darüber nachzudenken.

Alle haben eine Startkonstante, die ihren Startpunkt auf der Y-Achse bestimmt. Jedes hat auch eine kritische Konstante die bestimmt, wie schnell es zunimmt.$C$

• Für , C bestimmt die Zeit.$O(1)$$C$
• ist wirklich C × n , wobei C den Winkel bestimmt.$O(n)$$C \times n$$C$
• ist wirklich ( C × n ) 2 , wobei C die Schärfe der Kurve bestimmt.$O(n^2)$$(C \times n)^2$$C$

Um zu bestimmen, welchen Algorithmus Sie verwenden sollten, müssen Sie die Stelle abschätzen, an der sich die Laufzeiten schneiden. Beispielsweise verliert eine -Lösung mit einer hohen Startzeit oder einem hohen C an eine O ( n ) -Lösung mit einer niedrigen Startzeit und einem niedrigen C bei einer relativ großen Anzahl von Elementen.$O(1)$$C$$O(n)$$C$

Hier ist ein Beispiel aus der Praxis. Sie müssen einen Haufen Steine ​​über einen Hof bewegen. Sie können sie einzeln mit Ihren Händen bewegen oder mit einem großen, langsamen Baggerlader auf einmal heben und überfahren. Was ist Ihre Antwort, wenn es drei Steine ​​gibt? Was ist Ihre Antwort, wenn es dreitausend gibt?

Hier ist ein CS-Beispiel. Angenommen, Sie benötigen eine Liste, die immer sortiert ist. Sie könnten einen Baum verwenden, der sich in der Reihenfolge . Oder Sie können eine unsortierte Liste verwenden und nach jedem Einfügen oder Löschen bei O ( n log n ) neu sortieren . Da Baumoperationen kompliziert sind (sie haben eine hohe Konstante) und die Sortierung so einfach ist (niedrige Konstante), wird die Liste wahrscheinlich Hunderte oder Tausende von Elementen enthalten.$O(\log{n})$$O(n \log{n})$

Sie können so etwas beobachten, aber am Ende ist Benchmarking das, was es tun wird. Sie müssen auch die Anzahl der Artikel ermitteln, die Sie normalerweise haben, und das Risiko verringern, dass Sie mehr erhalten. Sie sollten auch Ihre Annahme dokumentieren, dass "die Leistung bei Elementen rapide abnimmt" oder "wir nehmen eine maximale festgelegte Größe von X an ".$X$$X$

Da sich diese Anforderungen ändern können, ist es wichtig, diese Art von Entscheidungen hinter eine Schnittstelle zu stellen. Machen Sie im obigen Baum- / Listenbeispiel den Baum oder die Liste nicht verfügbar. Auf diese Weise können Sie Ihre Meinung ändern, wenn sich Ihre Annahmen als falsch herausstellen oder Sie einen besseren Algorithmus finden. Sie können sogar einen hybriden und dynamischen Algorithmuswechsel durchführen, wenn die Anzahl der Elemente zunimmt.

Dies ist weitgehend huckepack auf die bereits geposteten Antworten, kann aber eine andere Perspektive bieten.

Es ist aufschlussreich, dass die Frage "ausreichend kleine Werte von n " diskutiert . Der springende Punkt von Big-O ist, zu beschreiben, wie die Verarbeitung in Abhängigkeit von der Verarbeitung wächst. Wenn die verarbeiteten Daten klein bleiben, ist es irrelevant, das Big-O zu diskutieren, da Sie nicht am Wachstum interessiert sind (was nicht geschieht).

Anders ausgedrückt: Wenn Sie nur eine kurze Strecke die Straße entlang fahren, ist es möglicherweise genauso schnell, zu Fuß, mit dem Fahrrad oder mit dem Auto zu fahren. Es kann sogar schneller gehen, wenn es eine Weile dauern würde, Ihre Autoschlüssel zu finden, oder wenn Ihr Auto Benzin benötigt usw.

Verwenden Sie für kleine n , was auch immer bequem ist.

Wenn Sie eine Überlandreise unternehmen, müssen Sie nach Möglichkeiten suchen, um Ihr Fahren, Ihren Kraftstoffverbrauch usw. zu optimieren.

Das Zitat ist eher vage und ungenau. Es gibt mindestens drei verwandte Arten, wie es interpretiert werden kann.

$k$, es ist ungültig) und dann die Antwort in der Tabelle nachschlagen (was konstant viel Zeit in Anspruch nimmt: Es gibt eine feste Anzahl von Einträgen in der Tabelle). Beachten Sie jedoch, dass die tatsächliche Größe der Tabelle wahrscheinlich unüberschaubar groß ist. Ich sagte, es gibt nur eine endliche Anzahl von Graphen auf hundert Eckpunkten, und das ist wahr. Es ist nur so, dass die endliche Zahl größer ist als die Anzahl der Atome im beobachtbaren Universum.

$\Theta(n^2)$ $cn^2$$C$$n_0$$n\geq n_0$$cn^2$$n_0=100,000,000$$n$$n^2 < 1000n$$O(n^{2.3729})$ $O(n^{2.8074})$

$n$$n^2$$n^3$$\Theta(n^2)$Der Algorithmus wird immer noch nur einige Dutzend Millionen Anweisungen zum Sortieren Ihrer Daten benötigen, was auf einer CPU, die Milliarden von Anweisungen pro Sekunde ausführen kann, nicht viel Zeit ist. OK, es gibt auch Speicherzugriffe, aber selbst ein langsamer Algorithmus dauert weniger als eine Sekunde. Daher ist es wahrscheinlich besser, einen einfachen, langsamen Algorithmus zu verwenden und ihn richtig zu machen, als einen komplexen, schnellen Algorithmus zu verwenden und festzustellen, dass er blitzschnell ist aber fehlerhaft und sortiert die Daten nicht richtig.

$f (n) = O (n^2)$$n_0$$f (n) < c n^2$$n > n_0$

$c n^2$$n^2 + 10^{18}$

Wenn Sie jedoch immer nur auf die Werte n = 1, 2 und 3 stoßen, spielt es in der Praxis keine Rolle, was f (n) für n ≥ 4 bedeutet. Sie können also auch f ( n) = O (1) mit c = max (f (1), f (2), f (3)). Und das ist, was ausreichend klein bedeutet: Wenn die Behauptung, dass f (n) = O (1), Sie nicht irreführt, wenn die einzigen Werte von f (n), denen Sie begegnen, "ausreichend klein" sind.

Wenn es nicht wächst, ist es O (1)

Die Aussage des Autors ist ein bisschen axiomatisch.

Wachstumsordnungen beschreiben, was mit der Menge an Arbeit passiert, die Sie mit Nzunehmender Geschwindigkeit erledigen müssen . Wenn Sie wissen, dass Ndas nicht zunimmt, ist Ihr Problem effektiv O(1).

Denken Sie daran, das O(1)heißt nicht "schnell". Ein Algorithmus, der immer 1 Billion Schritte benötigt, ist O(1). Ein Algorithmus, der 1 bis 200 Schritte benötigt, jedoch nie mehr O(1). [1]

Wenn Ihr Algorithmus genau N ^ 3Schritte ausführt und Sie wissen, dass Nnicht mehr als 5 Schritte ausgeführt werden dürfen, kann er niemals mehr als 125 Schritte ausführen, sodass er effektiv ist O(1).

Aber auch hier O(1)bedeutet das nicht unbedingt "schnell genug". Das ist eine separate Frage, die von Ihrem Kontext abhängt. Wenn es eine Woche dauert, bis etwas fertig ist, ist es Ihnen wahrscheinlich egal, ob es technisch ist O(1).

[1] O(1)Zum Beispiel bedeutet das Nachschlagen in einem Hash , obwohl Hash-Kollisionen bedeuten, dass Sie möglicherweise mehrere Elemente in einem Bucket durchsehen müssen, solange es eine feste Grenze für die Anzahl der Elemente in diesem Bucket gibt.

Jetzt kann ich eine Hashtabelle verwenden und O (1) Lookups haben (abgesehen von der spezifischen Implementierung der Hashtabelle), aber wenn ich zB eine Liste hätte, hätte ich O (n) Lookups. In Anbetracht dieses Axioms sind diese beiden identisch, wenn die Sammlungen klein genug sind. Aber irgendwann gehen sie auseinander ... was ist das für ein Punkt?

Praktisch ist es der Punkt, an dem das Erstellen der Hash-Tabelle mehr bringt als den Vorteil, den Sie durch die verbesserten Suchvorgänge erzielen. Dies hängt stark davon ab, wie oft Sie die Suche durchführen und wie oft Sie andere Aufgaben ausführen. O (1) vs O (10) ist keine große Sache, wenn Sie es einmal tun. Wenn Sie es tausende Male pro Sekunde tun, ist auch das von Bedeutung (obwohl es zumindest linear ansteigender Geschwindigkeit ist).

Während das Zitat wahr (aber vage) ist, gibt es auch Gefahren für sie. Imo sollten Sie die Komplexität in jeder Phase Ihrer Anwendung betrachten.

Es ist alles zu einfach zu sagen: Hey, ich habe nur eine kleine Liste. Wenn ich überprüfen möchte, ob Artikel A in der Liste enthalten ist, schreibe ich einfach eine einfache Schleife, um die Liste zu durchlaufen und die Artikel zu vergleichen.

Dann muss Ihr Buddy-Programmierer die Liste verwenden, sieht Ihre Funktion und sieht so aus: Hey, ich möchte keine Duplikate in der Liste, also verwendet er die Funktion für jedes Element, das der Liste hinzugefügt wird.

(Wohlgemerkt, es ist immer noch ein kleines Listenszenario.)

3 Jahre später komme ich und mein Chef hat gerade einen großen Verkauf gemacht: Unsere Software wird von einem großen nationalen Einzelhändler verwendet. Vorher haben wir nur kleine Läden gewartet. Und jetzt kommt mein Chef zu mir und flucht und schreit, warum die Software, die jetzt immer "gut funktioniert" hat, so schrecklich langsam ist.

Es stellte sich heraus, dass diese Liste eine Liste von Kunden war und unsere Kunden nur etwa 100 Kunden hatten, also bemerkte es niemand. Die Operation zum Auffüllen der Liste war im Grunde eine O (1) -Operation, da sie weniger als eine Millisekunde dauerte. Nun, nicht so sehr, wenn 10.000 Kunden hinzukommen.

Und Jahre nach der ursprünglichen schlechten O (1) -Entscheidung hätte das Unternehmen fast einen großen Kunden verloren. Alles wegen eines kleinen Konstruktions- / Vermutungsfehlers vor Jahren.

Die Motivation dafür basiert auf der falschen Vorstellung, dass O (1) immer besser ist als O (lg n), immer besser als O (n). Die asymptotische Reihenfolge einer Operation ist nur relevant, wenn unter realistischen Bedingungen das Problem tatsächlich groß wird.

Wenn ich zwei Algorithmen mit diesen Zeiten habe:

• log (n) +10000
• n + 1

Dann gibt es einen Punkt, an dem sie sich kreuzen. Bei nkleineren ist der "lineare" Algorithmus schneller und bei ngrößeren ist der "logarithmische" Algorithmus schneller. Viele Leute machen den Fehler anzunehmen, dass der logarithmische Algorithmus schneller ist, aber für kleine Leute ist dies nicht der Fall n.

Wenn n klein bleibt, ist jedes Problem O (1)!

Ich spekuliere, was hier gemeint ist, dass, wenn nes begrenzt ist, jedes Problem O (1) ist. Wenn wir zum Beispiel Ganzzahlen sortieren, können wir die Quicksortierung verwenden. O(n*log(n))offensichtlich. Aber wenn wir beschließen, dass es nie mehr als 2^64=1.8446744e+19ganze Zahlen geben kann, dann wissen wir, dass n*log(n)<= 1.8446744e+19*log(1.8446744e+19)<= 1.1805916e+21. Daher benötigt der Algorithmus immer weniger als 1.1805916e+21"Zeiteinheiten". Da dies eine konstante Zeit ist, können wir sagen, dass der Algorithmus immer in dieser konstanten Zeit ausgeführt werden kann -> O(1). (Beachten Sie, dass selbst wenn diese Zeiteinheiten Nanosekunden sind, dies eine Gesamtsumme von über 37411 Jahren ist.) Aber immer noch O(1).

Ich vermute, dass vielen dieser Antworten ein grundlegendes Konzept fehlt. O (1): O (n) ist nicht dasselbe wie f (1): f (n), wobei f dieselbe Funktion ist, da O keine einzelne Funktion darstellt. Selbst Schwerns schönes Diagramm ist nicht gültig, da es für alle Linien die gleiche Y-Achse hat. Um alle dieselbe Achse zu verwenden, müssten die Linien fn1, fn2 und fn3 sein, wobei jede eine Funktion ist, deren Leistung direkt mit der anderen verglichen werden kann.

Ich habe mehrmals gehört, dass für ausreichend kleine Werte von n O (n) so gedacht / behandelt werden kann, als wäre es O (1).

Nun, wenn n = 1 ist, sind sie genau gleich? Nein. Eine Funktion, die eine variable Anzahl von Iterationen zulässt, hat nichts mit einer Funktion gemein, die dies nicht tut.

Die Big-O-Notation drückt einfach aus, was passiert, wenn wir einen iterativen Prozess durchführen, und wie sich die Leistung (Zeit oder Ressourcen) verschlechtert, wenn 'n' zunimmt.

Zur Beantwortung der eigentlichen Frage würde ich sagen, dass diejenigen, die diese Behauptung aufstellen, die Big-O-Notation nicht richtig verstehen, da dies ein unlogischer Vergleich ist.

Hier ist eine ähnliche Frage: Wenn ich eine Zeichenfolge durchlaufe und weiß, dass meine Zeichenfolgen im Allgemeinen weniger als 10 Zeichen lang sind, kann ich sagen, dass dies das Äquivalent von O (1) ist, aber wenn meine Zeichenfolgen länger sind als ich würde sagen, es war O (n)?

Nein, da eine Zeichenfolge mit 10 Zeichen 10-mal so lang wie eine Zeichenfolge mit 1 Zeichen ist, jedoch 100-mal kürzer als eine Zeichenfolge mit 1000 Zeichen! Ist Zustand).

Ich glaube, der von Ihnen zitierte Text ist ziemlich ungenau (die Verwendung des Wortes "besser" ist normalerweise bedeutungslos, es sei denn, Sie geben den Kontext an: in Bezug auf Zeit, Raum usw.). Wie auch immer, ich glaube, die einfachste Erklärung wäre:

$O(1)$$O(1)$

Nehmen wir nun eine relativ kleine Menge von 10 Elementen und lassen Sie uns ein paar Algorithmen zum Sortieren verwenden (nur ein Beispiel). Nehmen wir an, wir halten die Elemente in einer Struktur, die uns auch einen Algorithmus zur Verfügung stellt, mit dem die Elemente in konstanter Zeit sortiert werden können. Angenommen, unsere Sortieralgorithmen können folgende Komplexitäten aufweisen (mit Big-O-Notation):

1. $O(1)$
2. $O(n)$
3. $O(nlog(n))$
4. $O(n^2)$

$O(1)$

Lassen Sie uns nun die wahren Komplexitäten der oben genannten Sortieralgorithmen "enthüllen" (wobei "wahr" bedeutet, dass die Konstante nicht ausgeblendet wird), dargestellt durch die Anzahl der Schritte, die zum Beenden erforderlich sind (und davon ausgehen, dass alle Schritte dieselbe Zeit in Anspruch nehmen):

1. $200$
2. $11n$
3. $4nlog(n)$
4. $1n^2$

Wenn unsere Eingabe die Größe 10 hat, sind dies die genauen Schritte für jeden oben genannten Algorithmus:

1. $200$
2. $11 \times 10 = 110$
3. $4 \times 10 \times 3.32 \approx 134$
4. $1 \times 100 = 100$

Wie Sie sehen, ist in diesem Fall der scheinbar schlechteste Algorithmus mit asympthotischer Komplexität der schnellste und schlägt Algorithmen mit O ( 1 ) , O ( n ) und O $O(n^2)$$O(1), O(n)$$O(nlog(n))$$O(n^2)$$O(1)$$O(n^2)$$O(1)$