Gibt es irgendwelche O(1/n)-Algorithmen?

Question

Gibt es irgendwelche O(1/n)-Algorithmen?

Oder etwas anderes, das kleiner als O(1) ist?

Answer 1

Diese Frage ist nicht so dumm, wie sie manchem erscheinen mag. Zumindest theoretisch kann etwas wie O (1/ n ) ist völlig sinnvoll, wenn man die mathematische Definition des Big-O-Notation :

Jetzt können Sie leicht ersetzen g ( x ) für 1/ x es ist offensichtlich, dass die obige Definition immer noch für einige gilt f .

Für die Abschätzung des asymptotischen Laufzeitwachstums ist dies weniger praktikabel ein sinnvoller Algorithmus kann nicht schneller werden, wenn die Eingabe wächst. Natürlich kann man einen beliebigen Algorithmus konstruieren, der dies erfüllt, z. B. den folgenden:

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

Es ist klar, dass diese Funktion mit zunehmender Größe der Eingabe immer weniger Zeit benötigt zumindest bis zu einer gewissen Grenze, die durch die Hardware erzwungen wird (Genauigkeit der Zahlen, Minimum an Zeit, die sleep warten kann, Zeit für die Verarbeitung von Argumenten usw.): Diese Grenze wäre dann eine konstante Untergrenze, so dass die obige Funktion encore hat Laufzeit O (1).

Aber es gibt son in der Praxis Algorithmen, bei denen die Laufzeit (zumindest teilweise) abnimmt, wenn die Eingabegröße zunimmt. Beachten Sie, dass diese Algorithmen no das folgende Laufzeitverhalten aufweisen O (1), allerdings. Dennoch sind sie interessant. Nehmen wir zum Beispiel den sehr einfachen Textsuchalgorithmus von Horspool . Hier sinkt die erwartete Laufzeit mit zunehmender Länge des Suchmusters (mit zunehmender Länge des Heuhaufens steigt die Laufzeit jedoch wieder).

Answer 2

Sharptooth hat recht, O(1) ist die bestmögliche Leistung. Dies bedeutet jedoch keine schnelle Lösung, sondern nur eine Lösung mit fester Zeit.

Eine interessante Variante, und vielleicht ist es das, was wirklich vorgeschlagen wird, ist, welche Probleme einfacher wenn die Bevölkerung wächst. Mir fällt 1 Antwort ein, wenn auch eine konstruierte und augenzwinkernde:

Haben zwei Personen in einem Set den gleichen Geburtstag? Wenn n größer als 365 ist, wird true zurückgegeben. Für weniger als 365 ist dies jedoch O(n ln n). Vielleicht keine gute Antwort, da das Problem nicht langsam einfacher wird, sondern für n > 365 einfach O(1) wird.

Answer 3

Das ist nicht möglich. Die Definition von Big-O ist die nicht größer als Ungleichheit:

A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)

B(n) ist also der Maximalwert, und wenn er mit zunehmendem n abnimmt, ändert sich die Schätzung nicht.

Answer 4

Nach meinen bisherigen Kenntnissen der Big-O-Notation ist selbst ein einziger Schritt (z. B. das Überprüfen einer Variablen oder das Ausführen einer Zuweisung) O(1).

Beachten Sie, dass O(1) dasselbe ist wie O(6), da die "Konstante" keine Rolle spielt. Deshalb sagen wir auch, dass O(n) dasselbe ist wie O(3n).

Wenn Sie also auch nur 1 Schritt benötigen, ist das O(1)... und da Ihr Programm mindestens 1 Schritt benötigt, ist das Minimum, das ein Algorithmus erreichen kann, O(1). Es sei denn, wir tun es nicht, dann ist es O(0), denke ich? Wenn wir überhaupt etwas tun, dann ist es O(1), und das ist das Minimum, das er erreichen kann.

(Wenn wir uns dafür entscheiden, es nicht zu tun, kann es eine Zen- oder Tao-Frage werden... im Bereich der Programmierung ist O(1) immer noch das Minimum).

Oder wie wäre es hiermit:

Programmierer Chef, ich habe einen Weg gefunden, dies in O(1) Zeit zu tun!
Chef : Das ist nicht nötig, wir sind heute Morgen bankrott.
Programmierer Oh, dann wird es O(0).

Answer 5

Nein, das ist nicht möglich:

Da n in 1/n gegen unendlich tendiert, erreichen wir schließlich 1/(inf), was effektiv 0 ist.

Somit wäre die Big-Oh-Klasse des Problems O(0) bei einem massiven n, aber näher an konstanter Zeit bei einem niedrigen n. Dies ist nicht sinnvoll, da das einzige, was in schneller als konstanter Zeit erledigt werden kann, ist:

void nothing() {};

Und selbst das ist umstritten!

Sobald Sie einen Befehl ausführen, befinden Sie sich in mindestens O(1), also nein, wir können keine Big-Oh-Klasse von O(1/n) haben!