Was bedeutet "O (1) Zugriffszeit"?

https://stackoverflow.com/questions/697918

big-o

22-08-2019
|

Frage

Ich habe diesen Begriff "O (1) Zugriffszeit" gesehen, das früher "schnell" bedeutet, aber ich verstehe nicht, was er bedeutet. Der andere Begriff, den ich im selben Kontext damit sehe, ist "O (n) Zugriffszeit". Könnte jemand bitte auf einfache Weise erklären, was diese Begriffe bedeuten?

Siehe auch

Was ist eine große O -Notation? Benutzt du es?

Big-o für achtjährige?

Lösung

Sie werden sich über die Reihenfolge der Komplexität nachlesen wollen.

http://en.wikipedia.org/wiki/big_o_notation

Kurz gesagt, O (1) bedeutet, dass es eine konstante Zeit dauert, wie 14 Nanosekunden oder drei Minuten unabhängig von der Datenmenge im Satz.

O (n) bedeutet, dass es eine lineare Zeit mit der Größe des Satzes dauert, sodass ein Satz so doppelt so groß ist. Sie möchten wahrscheinlich keine Million Objekte in eines davon geben.

Andere Tipps

Im Wesentlichen bedeutet dies, dass es die gleiche Zeit dauert, um einen Wert in Ihrer Sammlung nachzuschlagen, unabhängig davon, ob Sie eine kleine Anzahl von Elementen in Ihrer Sammlung oder sehr viele (in den Einschränkungen Ihrer Hardware) haben.

O (n) würde bedeuten, dass die Zeit, die zum Nachschlagen eines Gegenstands benötigt wird, proportional zur Anzahl der Elemente in der Sammlung ist.

Typische Beispiele für diese sind Arrays, auf die unabhängig von ihrer Größe direkt zugegriffen werden kann, und verknüpfte Listen, die von Anfang an in Ordnung zu Zugang zu einem bestimmten Element durchquert werden müssen.

Die andere Operation, die normalerweise diskutiert wird, ist einsatz. Eine Sammlung kann O (1) für den Zugriff, O (n) für den Einsatz sein. Tatsächlich hat ein Array genau dieses Verhalten, da Sie jedes Element nach rechts einfügen müssen, indem Sie ihn in den folgenden Slot kopieren.

Jede Antwort, die derzeit auf diese Frage antwortet O(1) bedeutet eine konstante Zeit (was auch immer es mit Messung passiert; könnte Laufzeit, Anzahl der Operationen usw. sein). Dies ist nicht genau.

Zu sagen, dass die Laufzeit ist O(1) bedeutet, dass es eine Konstante gibt c so dass die Laufzeit oben von oben begrenzt wird c, unabhängig von der Eingabe. Zum Beispiel die Rückgabe des ersten Elements eines Arrays von n Ganzzahlen sind O(1):

int firstElement(int *a, int n) {
    return a[0];
}

Aber diese Funktion ist O(1) zu:

int identity(int i) {
    if(i == 0) {
        sleep(60 * 60 * 24 * 365);
    }
    return i;
}

Die Laufzeit hier ist um 1 Jahr oben begrenzt, aber die Laufzeit befindet sich in der Reihenfolge der Nanosekunden.

Zu sagen, dass die Laufzeit ist O(n) bedeutet, dass es eine Konstante gibt c so dass die Laufzeit oben von oben begrenzt wird c * n, wo n misst die Größe des Eingangs. Zum Beispiel die Anzahl der Vorkommen einer bestimmten Ganzzahl in einem ungewöhnlichen Array von finden n Ganzzahlen durch den folgenden Algorithmus sind O(n):

int count(int *a, int n, int item) {
    int c = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] == item) c++;
    }
    return c;
}

Dies liegt daran, dass wir durch das Array iterieren müssen, das jedes Element einzeln inspiziert.

O (1) bedeutet, dass die Zeit für den Zugriff auf etwas unabhängig von der Anzahl der Elemente in der Sammlung ist.

O (n) würde bedeuten, dass die Zeit für den Zugriff auf ein Element proportional zur Zahl (n) der Elemente in der Sammlung ist.

O (1) bedeutet nicht unbedingt "schnell". Es bedeutet, dass die Zeit, die sie benötigt, konstant und nicht Basierend auf der Größe der Eingabe in die Funktion. Konstante kann schnell oder langsam sein. O (n) bedeutet, dass sich die Zeit, die die Funktion benötigt, in direktem Verhältnis zur Größe der Eingabe in die Funktion ändert, die mit n bezeichnet wird. Auch hier könnte es schnell oder langsam sein, aber es wird langsamer, wenn die Größe von N zunimmt.

Es heißt das Big O Notation, und beschreibt die Suchzeit für verschiedene Algorithmen.

O (1) bedeutet, dass die schlimmste Falllaufzeit konstant ist. Für die meisten Situationen bedeutet dies, dass Sie die Sammlung nicht in der Lage sind. Sie finden Sie nicht, wonach Sie sofort suchen.

"Big O Notation" ist eine Möglichkeit, die Geschwindigkeit von Algorithmen auszudrücken. n ist die Datenmenge, mit der der Algorithmus arbeitet. O(1) bedeutet, dass es, egal wie viel Daten, in ständiger Zeit ausgeführt werden. O(n) bedeutet, dass es proportional zur Datenmenge ist.

O(1) Immer gleichzeitig unabhängig vom Datensatz n durchführen. Ein Beispiel für O (1) wäre eine ArrayList, die mit Index auf sein Element zugreift.

O(n) Auch als lineare Reihenfolge bezeichnet, wächst die Leistung linear und in direktem Verhältnis zur Größe der Eingabedaten. Ein Beispiel für O (n) wäre eine ArrayList -Einfügung und Löschung in zufälliger Position. Da jede nachfolgende Einführung/Löschung in zufälliger Position dazu führt, dass die Elemente in der Arraylist nach rechts von seinem internen Array verlagern, um ihre lineare Struktur aufrechtzuerhalten Zu Neuarray, das teure Verarbeitungszeit in Anspruch nimmt, nimmt die Leistung zu.

Grundsätzlich bedeutet O (1), dass seine Berechnungszeit konstant ist, während O (n) bedeutet, dass es abhängt direkt Bei der Größe des Eingangs - dh durch ein Array hat O (n) - nur Schleifen -, da es von der Anzahl der Elemente abhängt, während das Maximum zwischen normalen Zahlen o (1) berechnet wird.

Wikipedia könnte auch helfen: http://en.wikipedia.org/wiki/computational_complexity_theory

Der einfachste Weg, O (1) und O (n) zu unterscheiden, ist das Vergleich von Array und Liste.

Wenn Sie für Array den richtigen Indexwert haben, können Sie sofort auf die Daten zugreifen. (Wenn Sie den Index nicht kennen und durch das Array schleifen müssen, wird es nicht mehr o (1) sein)

Für die Liste müssen Sie ihn immer durchlaufen, unabhängig davon, ob Sie den Index kennen oder nicht.

Es bedeutet, dass die Zugriffszeit konstant ist. Unabhängig davon, ob Sie aus 100 oder 100.000 Datensätzen zugreifen, ist die Abrufzeit dieselbe.

Im Gegensatz dazu würde O (n) Zugriffszeit darauf hinweisen, dass die Abrufzeit direkt proportional zu der Anzahl der Datensätze ist, auf die Sie zugreifen.

Dies bedeutet, dass der Zugriff ständige Zeit in Anspruch nimmt. IE hängt nicht von der Größe des Datensatzes ab. O (n) bedeutet, dass der Zugriff von der Größe des Datensatzes linear abhängt.

Das O ist auch als Big-O bekannt.

Einführung in Algorithmen: Zweite Ausgabe von Cormen, Leiserson, Rivest & Stein sagt auf Seite 44 das

Da jede Konstante ein Grad-0-Polynom ist, können wir jede konstante Funktion als Theta (n^0) oder Theta (1) ausdrücken. Diese letztere Notation ist jedoch ein geringfügiger Missbrauch, da nicht klar ist, welche Variable die Unendlichkeit tendiert. Wir werden häufig die Notation Theta (1) verwenden, um entweder eine Konstante oder eine konstante Funktion in Bezug auf eine Variable zu bedeuten. ... Wir bezeichnen durch o (g (n)) ... die Menge der Funktionen f (n), so dass es positive Konstanten c und n0 gibt, so dass 0 <= f (n) <= c*g (n) für alle n> = n0. ... Beachten Sie, dass f (n) = theta (g (n)) f (n) = o (g (n)) impliziert, da die Notation theta stärker ist als o Notation.

Wenn ein Algorithmus in o (1) Zeit läuft, bedeutet dies, dass asymptotisch nicht von einer Variablen abhängt, was bedeutet für Werte von n über einer bestimmten Menge. Technisch gesehen ist es o (n^0) Zeit.

Hier ist eine einfache Analogie; Stellen Sie sich vor, Sie laden Filme online herunter, mit O (1). Wenn es 5 Minuten dauert, einen Film herunterzuladen, dauert es immer noch genauso, bis 20 Filme heruntergeladen werden. Es spielt also keine Rolle, wie viele Filme Sie herunterladen. Sie werden gleich (5 Minuten) dauern, ob es sich um einen oder 20 Filme handelt. Ein normales Beispiel für diese Analogie ist, wenn Sie in eine Filmbibliothek gehen, unabhängig davon, ob Sie einen Film nehmen oder 5, Sie sie einfach gleichzeitig auswählen. Daher gleichzeitig verbringen.

Wenn O (N), wenn es 5 Minuten dauert, einen Film herunterzuladen, dauert es ungefähr 50 Minuten, um 10 Filme herunterzuladen. Die Zeit ist also nicht konstant oder irgendwie proportional zur Anzahl der Filme, die Sie herunterladen.

O (1) bedeutet zufälligen Zugriff. In jedem Zufallszugriffsspeicher ist die Zeit, die benötigt wird, um an einem beliebigen Ort auf ein Element zuzugreifen, gleich. Hier kann die Zeit eine ganze Zahl sein, aber das einzige, was man sich erinnern muss, ist die Zeit, die das Element an (n-1) Th- oder N-ten Standort abzurufen (dh konstant).

Während O (n) von der Größe von n abhängig ist.

Nach meiner Perspektive,

O (1) bedeutet Zeit, jeweils eine Operation oder Anweisung auszuführen, eine zeitkomplexe Analyse des Algorithmus für den besten Fall.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow