Wie kann f (n)

Question

Ich habe gelesen Dieses Tutorial in der Zeit Komplexität , und ich bin ein bisschen verwirrt von seiner Erklärung des großen $ o $ Notation. Es schreibt:

$ o (g (n))= $ { $ f (n) $ : dort existieren positive Konstanten $ C $ und $ n_0 $ so, dass $ 0 \ leq f (n) \ leq c * g (n) $ für alle $ n> n_0 $ .

Die Art und Weise, wie ich es verstehe, $ C * g (n) $ zeigt $ C $ multipliziert von $ g (n) $ . Wenn dies der Fall ist, wie wird der obige Ausdruck dann die Zeit angeben, und nicht nur der $ C * g (n) $ ist größer als $ F (n) $ ? Oder bin ich falsch, und das ist eine Notisierung, die ich nicht verstehe? Mein Verständnis der Zeitkomplexität ist sehr rudimentär, also vergib mir, wenn dies nur ein dummer Fehler in meiner Seite ist.

Answer 1

Wie spielt f (n)

es nicht. Bachmann-Landau-Notation ist einfach ein praktischer Weg, um die Wachstumspreise zu vergleichen. Es sagt nichts über was diese Funktionen bedeuten , und wir können ziemlich sicher sein, dass Bachmann nicht an Computer nachgedacht, als er 1894 mit sich kam.

Welche Bedeutung Sie zuordnen, wenden Sie sich an diese Funktionen. Wenn zum Beispiel Vergleichsvergleichs-Sortieralgorithmen, nehmen wir normalerweise $ n $ , um die Anzahl der Elemente in der Sammlung und $ f (n) $ , um die Anzahl der Vergleiche oder die Anzahl der Swaps oder die Anzahl der Vergleiche und Swaps zu sein.

Hinweis auch, dass all dies immer relativ zu einem Maschinenmodell oder einem Kostenmodell ist.

Als ein sehr einfaches Beispiel, wenn ich Sie fragen würde, was ist der algorithmische SCHLECHTE-STEP-Komplexität für das Kopieren einer Liste, sagen Sie $ O (n) $ . Tatsächlich wäre die richtige Antwort wäre "Ich kann Ihnen nicht sagen, weil Sie das Maschinenmodell noch nicht angegeben haben". Denn beispielsweise in einer Turing-Maschine, ist das Kopieren einer Liste $ O (N ^ 2) $ , da für jedes kopierte Element der Kopf des TM ist weiter und weiter fahren, um das Ende der Liste zu erreichen, um das nächste Element zu schreiben.

Answer 2

sagt, dass die Laufzeit eines Algorithmus in $ O (g (n)) $ gibt, wie Sie, wie Sie es nicht bemerkt haben, nur eine obere Grenze. Darüber hinaus erfolgt die obere Grenze mit den Konstanten $ C $ und $ n_0 $ unbekannt. Ja, ja, es ist eine ziemlich schwache Information über die Laufzeit.

Die nicht angegebene Konstante $ C $ kann die Informationen über die realen Kosten der Grundvorgänge des Algorithmus enthalten, der zwischen Läufen unbekannt und / oder variabel sein kann, Aber auch bekannter Zeit, um einen Zeitraum zu kosten, der begrenzt ist. Die nicht näherifizierte Konstante $ N_0 $ $ spiegelt wider, dass die angegebene gebundene Größe auf große Größen des Eingangs (oder der Parameter $ N $ <) bezieht / span> repräsentiert).

Andere Symbole werden verwendet, um andere Arten zu geben Genauere Informationen zur Laufzeit.