WikiDer > Konstante Zeit

In dem Komplexitätstheorie kann a Algorithmus im konstante Zeit oder O(1) time, wenn die benötigte Zeit nicht von der Größe der Eingabe abhängt. Das Ausführen eines solchen Algorithmus erfordert unabhängig von der Größe der Eingabe eine konstante Zeit. Beispiele hierfür sind das Anfordern eines Elements von a Array, Abfrage des ersten Elements von a verlinkte Liste oder prüfen, ob a natürliche Zahl im binäre NotationEin bisschen ist.

Suche nach einem Element in a unsortiertaufführen läuft nicht in konstanter Zeit, da ggf. das Durchlaufen der gesamten Liste erforderlich ist und die benötigte Zeit daher von der Anzahl der Elemente abhängt, nein, In der Liste. Das Nachschlagen eines Elements in einer unsortierten Liste erfolgt in lineare Zeit, Ö(nein), da sie linear von abhängt nein. Dieses Art der Suche heißt daher auch lineare Suche erwähnt.

Definition

Ein Algorithmus kann in konstanter Zeit ausgeführt werden, wenn es eine Konstante gibt c existiert so, dass die Anzahl der Operationen dadurch begrenzt ist c. Diese Konstante c kann je nach Algorithmus variieren. Das Komplexitätsgrad wird auch als O(1) notiert.

Ein Algorithmus, der A(nein) Operationen erforderlich, wobei nein ist der Betrag der Eingabe wird in O(1) Zeit ausgeführt, wenn 0 ≤ A(nein) ≤ c, für alle nein und eine Konstante c.

Eigenschaften

Wiederholen

Wenn ein Algorithmus in konstanter Zeit ausgeführt wird, bedeutet das nicht, dass bestimmte Dinge nicht mehrmals passieren. Es ist durchaus möglich, eine Operation mehrmals in einer konstanten Zeit auszuführen, solange diese Anzahl nicht von der Eingabe abhängt. Beispiel: Anfordern von genau 100 Elementen aus einem Array; Das Abrufen eines Elements aus einem Array erfolgt in konstanter Zeit und 100 ist eine feste Konstante, die nicht von der Größe des Arrays abhängt. Der Algorithmus als Ganzes geschieht somit in konstanter Zeit. Dies wird immer noch als O(1) notiert und nicht als O(100).

Folgendes passiert auch in konstanter Zeit:

zum x = 1 zu 100:zum y = 1 zu 200: Betrieb in konstanter Zeit ausführen

Die Anzahl von Malen, die der Vorgang ausgeführt wird, beträgt nämlich 100 * 200 Mal (eine konstante Anzahl) und der Vorgang selbst erfolgt ebenfalls in konstanter Zeit.

Die benötigte Zeit kann variieren

Es ist möglich, dass die benötigte Zeit je nach Eingang unterschiedlich ist, solange die benötigte Zeit immer durch eine Konstante begrenzt wird c. Ein Beispiel ist das folgende Stück Pseudocode, wobei a und b Zahlen sind:

wenn (b < a) vertausche a und b

Nach der Ausführung dieses Codes ist a b. Wenn für die eingegebenen Zahlen a und b gilt, dass a b, dann werden die Zahlen nicht vertauscht. Der Algorithmus läuft dann immer noch in konstanter Zeit, denn es gibt eine Konstante c so dass die benötigte Zeit durch diese Konstante begrenzt ist. Im schlimmsten Fall findet sowohl das Prüfen von a und b als auch das Vertauschen statt; die dafür benötigte Zeit beträgt höchstens c Operationen. Im besten Fall wird nur die Prüfung auf a und b durchgeführt, die sicherlich kleiner ist als die Konstante c.

Siehe auch

• Komplexitätsgrad