Gibt es O (1 / n) -Algorithmen?

335

Gibt es O (1 / n) -Algorithmen?

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

Peter Mortensen
quelle
Bei den meisten Fragen wird davon ausgegangen, dass Sie meinen: "Gibt es Algorithmen mit einer Zeitkomplexität von O (1 / n)?" Sollen wir annehmen, dass dies der Fall ist? Big-O (und Big-Theta usw.) beschreiben Funktionen, keine Algorithmen. (Ich kenne keine Äquivalenz zwischen Funktionen und Algorithmen.)
Jyoungdev
4
Dies ist die allgemein verständliche Definition des "O (X) -Algorithmus" in der Informatik: ein Algorithmus, dessen zeitliche Komplexität O (X) ist (für einige Ausdrücke X).
David Z
2
Ich habe eine solche Bindung im Falle eines E / A-Algorithmus mit effizienter Prioritätswarteschlange unter Verwendung von Buffer Tree gehört. In einem Pufferbaum benötigt jede Operation O (1 / B) I / Os; wobei B die Blockgröße ist. Die Gesamtzahl der E / A für n Operationen beträgt O (n / B.log (Basis M / B) (n / B)), wobei der Log-Teil die Höhe des Pufferbaums ist.
CODError
Es gibt viele Algorithmen mit einer Fehlerwahrscheinlichkeit von O (1 / n). Zum Beispiel ein Bloom-Filter mit O (n log n) Eimern.
Thomas Ahle
Sie können ein Ei nicht schneller legen, indem Sie Hühner hinzufügen.
Wyck

Antworten:

310

Diese Frage ist nicht so dumm, wie es scheinen mag. Zumindest theoretisch ist etwas wie O (1 / n ) völlig sinnvoll, wenn wir die mathematische Definition der Big O-Notation nehmen :

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

Für die Schätzung des asymptotischen Laufzeitwachstums ist dies weniger praktikabel. Ein aussagekräftiger Algorithmus kann nicht schneller werden, wenn die Eingabe wächst. Natürlich können Sie einen beliebigen Algorithmus erstellen, um dies zu erfüllen, z. B. den folgenden:

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

Es ist klar, dass diese Funktion weniger Zeit benötigt, wenn die Eingabegröße zunimmt… zumindest bis zu einem von der Hardware erzwungenen Grenzwert (Genauigkeit der Zahlen, minimale sleepWartezeit, Zeit für die Verarbeitung von Argumenten usw.): Dieser Grenzwert wäre dann a konstante Untergrenze, so dass die obige Funktion immer noch Laufzeit O (1) hat.

Tatsächlich gibt es jedoch reale Algorithmen, bei denen die Laufzeit (zumindest teilweise) mit zunehmender Eingabegröße abnehmen kann. Beachten Sie jedoch, dass diese Algorithmen kein Laufzeitverhalten unterhalb von O (1) aufweisen. Trotzdem sind sie interessant. Nehmen Sie zum Beispiel den sehr einfachen Textsuchalgorithmus von Horspool . Hier nimmt die erwartete Laufzeit mit zunehmender Länge des Suchmusters ab (eine zunehmende Länge des Heuhaufens erhöht jedoch erneut die Laufzeit).

Konrad Rudolph
quelle
22
"Durch die Hardware erzwungen" gilt auch für eine Turingmaschine. Im Fall von O (1 / n) gibt es immer eine Eingabegröße, für die der Algorithmus keine Operation ausführen soll. Und deshalb würde ich denken, dass eine O (1 / n) -Zeitkomplexität tatsächlich unmöglich zu erreichen ist.
Roland Ewald
28
Mehrdad, du verstehst nicht. Die O-Notation ist etwas über die Grenze (technisch begrenzt) als n -> ∞. Die Laufzeit eines Algorithmus / Programms ist die Anzahl der Schritte auf einer Maschine und daher diskret - es gibt eine Untergrenze ungleich Null für die Zeit, die ein Algorithmus benötigen kann ("ein Schritt"). Es ist möglich, dass ein Programm bis zu einem endlichen N eine Anzahl von Schritten ausführt, die mit n abnehmen, aber der einzige Weg, wie ein Algorithmus O (1 / n) oder tatsächlich o (1) sein kann, besteht darin, dass er für alle ausreichend Zeit 0 benötigt großes n - was nicht möglich ist.
ShreevatsaR
28
Wir sind nicht anderer Meinung, dass O (1 / n) -Funktionen (im mathematischen Sinne) existieren. Offensichtlich tun sie es. Die Berechnung ist jedoch von Natur aus diskret. Etwas, das eine Untergrenze hat, wie die Laufzeit eines Programms - entweder auf der von Neumann-Architektur oder einer rein abstrakten Turing-Maschine - kann nicht O (1 / n) sein. Entsprechend kann etwas, das O (1 / n) ist, keine Untergrenze haben. (Ihre "Schlaf" -Funktion muss aufgerufen werden, oder die Variable "Liste" muss untersucht werden - oder das Eingabeband muss auf einer Turing-Maschine untersucht werden. Die benötigte Zeit würde sich also mit n als etwas ε + 1 / ändern. n, das ist nicht O (1 / n))
ShreevatsaR
16
Wenn T (0) = ∞, hört es nicht auf. Es gibt kein "T (0) = ∞, aber es hält immer noch an". Selbst wenn Sie in R∪ {∞} arbeiten und T (0) = ∞ und T (n + 1) = T (n) / 2 definieren, gilt T (n) = ∞ für alle n. Lassen Sie mich wiederholen: Wenn eine diskrete Funktion O (1 / n) ist, dann ist sie für alle ausreichend großen n 0. [Beweis: T (n) = O (1 / n) bedeutet, dass es eine Konstante c gibt, so dass für n> N0 ist T (n) <c (1 / n), was bedeutet, dass für jedes n> max (N0,1 / c) T (n) <1, was T (n) = 0 bedeutet.] Keine Maschine, real oder abstrakt, kann 0 Zeit in Anspruch nehmen: Sie muss die Eingabe betrachten. Nun, außer der Maschine, die niemals etwas tut und für die T (n) = 0 für alle n ist.
ShreevatsaR
43
Sie müssen jede Antwort mögen, die beginnt: "Diese Frage ist nicht so dumm, wie es scheinen mag."
Telemachos
138

Ja.

Es gibt genau einen Algorithmus mit Laufzeit O (1 / n), den "leeren" Algorithmus.

Wenn ein Algorithmus O (1 / n) ist, bedeutet dies, dass er asymptotisch in weniger Schritten ausgeführt wird als der Algorithmus, der aus einem einzelnen Befehl besteht. Wenn es für alle n> n0 in weniger als einem Schritt ausgeführt wird, darf es für diese n überhaupt keine Anweisung enthalten. Da die Prüfung 'wenn n> n0' mindestens 1 Befehl kostet, darf sie für alle n keinen Befehl enthalten.

Fazit: Der einzige Algorithmus, der O (1 / n) ist, ist der leere Algorithmus, der aus keiner Anweisung besteht.

Tobias
quelle
2
Wenn also jemand nach der zeitlichen Komplexität eines leeren Algorithmus fragt, antworten Sie mit O (1 / n) ??? Irgendwie bezweifle ich das.
Phkahler
24
Dies ist die einzig richtige Antwort in diesem Thread und (trotz meiner positiven Bewertung) bei null Stimmen. Dies ist StackOverflow, bei dem "richtig aussehende" Antworten höher bewertet werden als tatsächlich richtige.
ShreevatsaR
5
Nein, es ist mit 0 bewertet, weil es falsch ist. Es ist falsch, einen Big-Oh-Wert in Bezug auf N auszudrücken, wenn er unabhängig von N ist. Zweitens benötigt das Ausführen eines Programms, auch eines gerade existierenden, mindestens eine konstante Zeit, O (1). Selbst wenn dies nicht der Fall wäre, wäre es O (0), nicht O (1 / n).
Kenj0418
32
Jede Funktion, die O (0) ist, ist auch O (1 / n) und auch O (n), auch O (n ^ 2), auch O (2 ^ n). Seufz, versteht niemand einfache Definitionen? O () ist eine Obergrenze.
ShreevatsaR
16
@ kenj0418 Du hast es geschafft, in jedem einzelnen Satz falsch zu liegen. "Es ist falsch, einen Big-Oh-Wert in Bezug auf N auszudrücken, wenn er unabhängig von N ist." Eine konstante Funktion ist eine vollkommen doofe Funktion. "Zweitens benötigt das Ausführen eines Programms, auch eines gerade existierenden, mindestens eine konstante Zeit, O (1)." Die Definition von Komplexität sagt nichts über das tatsächliche Ausführen von Programmen aus. "es wäre O (0), nicht O (1 / n)". Siehe den Kommentar von @ ShreevatsaR.
Alexey Romanov
25

Scharfzahn ist richtig, O (1) ist die bestmögliche Leistung. Dies bedeutet jedoch keine schnelle Lösung, sondern nur eine zeitlich festgelegte Lösung.

Eine interessante Variante, und vielleicht wird wirklich vorgeschlagen, welche Probleme mit wachsender Bevölkerung leichter werden . Ich kann mir eine, wenn auch erfundene und ironische Antwort vorstellen:

Haben zwei Personen in einem Set denselben Geburtstag? Wenn n 365 überschreitet, geben Sie true zurück. Obwohl für weniger als 365, ist dies O (n ln n). Vielleicht keine gute Antwort, da das Problem nicht langsam einfacher wird, sondern nur zu O (1) für n> 365 wird.

Adrian
quelle
7
366. Schaltjahre nicht vergessen!
Nick Johnson
1
Du hast Recht. Wie Computer bin ich gelegentlich Rundungsfehlern ausgesetzt :-)
Adrian
10
+1. Es gibt eine Reihe von NP-vollständigen Problemen, die mit zunehmendem n einen "Phasenübergang" durchlaufen, dh sie werden schnell viel einfacher oder schwieriger, wenn Sie einen bestimmten Schwellenwert von n überschreiten. Ein Beispiel ist das Problem der Zahlenpartitionierung: Teilen Sie eine Menge von n nichtnegativen Ganzzahlen in zwei Teile auf, sodass die Summe jedes Teils gleich ist. Dies wird bei einem bestimmten Schwellenwert von n dramatisch einfacher.
j_random_hacker
23

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

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)

Das B (n) ist also tatsächlich der Maximalwert. Wenn es daher mit zunehmendem n abnimmt, ändert sich die Schätzung nicht.

Scharfzahn
quelle
42
Ich vermute, diese Antwort ist die "richtige", aber leider fehlt mir der Verstand, um sie zu verstehen.
Freiraum
12
AFAIK Diese Bedingung muss nicht für alle n gelten, sondern für alle n> n_0 (dh nur, wenn die Größe der Eingabe einen bestimmten Schwellenwert erreicht).
Roland Ewald
30
Ich sehe nicht, wie die Definition (sogar korrigiert) der Frage des OP widerspricht. Die Definition gilt für völlig beliebige Funktionen! 1 / n ist eine völlig sinnvolle Funktion für B, und tatsächlich widerspricht Ihre Gleichung dem nicht (rechnen Sie einfach nach). Nein, trotz viel Konsens ist diese Antwort tatsächlich falsch . Es tut uns leid.
Konrad Rudolph
10
Falsch! Ich mag kein Downvoting, aber Sie sagen, dass dies unmöglich ist, wenn es keinen klaren Konsens gibt. In der Praxis haben Sie Recht, wenn Sie eine Funktion mit 1 / n Laufzeit (einfach) erstellen, wird sie schließlich die Mindestzeit erreichen, was sie bei der Implementierung effektiv zu einem O (1) -Algorithmus macht. Nichts hindert den Algorithmus daran, auf dem Papier O (1 / n) zu sein.
Jheriko
3
@Jason: Ja, jetzt wo du es sagst ... :) @jheriko: Eine zeitliche Komplexität von O (1 / n) funktioniert meiner Meinung nach nicht auf Papier. Wir charakterisieren die Wachstumsfunktion f (Eingabegröße) = #ops für eine Turingmaschine. Wenn es nach x Schritten für eine Eingabe der Länge n = 1 anhält, wähle ich eine Eingabegröße n >> x, dh groß genug, dass, wenn der Algorithmus tatsächlich in O (1 / n) ist, keine Operation sein sollte erledigt. Wie sollte eine Turing-Maschine dies überhaupt bemerken (es ist nicht erlaubt, einmal vom Band zu lesen)?
Roland Ewald
16

Aus meiner vorherigen Erfahrung mit der Big-O-Notation geht hervor, dass O (1) ist, selbst wenn Sie einen Schritt benötigen (z. B. Überprüfen einer Variablen, Ausführen einer Zuweisung).

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

Wenn Sie also nur einen Schritt benötigen, ist das O (1) ... und da Ihr Programm mindestens einen Schritt benötigt, kann ein Algorithmus mindestens O (1) ausführen. Wenn wir es nicht tun, dann ist es O (0), denke ich? Wenn wir überhaupt etwas tun, dann ist es O (1), und das ist das Minimum, das es gehen kann.

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

Oder wie wäre es damit:

Programmierer : Chef, ich habe einen Weg gefunden, dies in O (1) Zeit zu tun!
Chef : Keine Notwendigkeit, wir sind heute Morgen bankrott.
Programmierer : Oh, dann wird es O (0).

動靜 能量
quelle
Ihr Witz erinnerte mich an etwas aus dem Tao der Programmierung: canonical.org/~kragen/tao-of-programming.html#book8 (8.3)
kenj0418
Ein Algorithmus, der aus Nullschritten besteht, ist O (0). Das ist ein sehr fauler Algorithmus.
Nalply
8

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) mit einem massiven n, aber näher an der konstanten Zeit mit einem niedrigen n. Dies ist nicht sinnvoll, da das einzige, was schneller als in konstanter Zeit erledigt werden kann, Folgendes ist:

void nothing() {};

Und auch das ist fraglich!

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

Ed James
quelle
7

Was ist, wenn die Funktion überhaupt nicht ausgeführt wird (NOOP)? oder mit einem festen Wert. Zählt das?

SpliFF
quelle
16
Das ist immer noch O (1) Laufzeit.
Konrad Rudolph
2
Richtig, das ist immer noch O (1). Ich sehe nicht ein, wie jemand das verstehen kann, und behaupte dennoch in einer anderen Antwort, dass etwas weniger als NO-OP möglich ist.
ShreevatsaR
4
ShreevatsaR: Es gibt absolut keinen Widerspruch. Sie scheinen nicht zu verstehen , dass die große O-Notation nichts mit der in der Funktion verbrachten Zeit zu tun hat. Sie beschreibt vielmehr, wie sich diese Zeit mit der Änderung der Eingabe (über einem bestimmten Wert) ändert . Weitere Informationen finden Sie in einem anderen Kommentarthread.
Konrad Rudolph
Ich verstehe es sehr gut, danke. Der Punkt - wie ich im anderen Thread mehrmals ausgeführt habe - ist, dass wenn die Zeit mit der Eingabe mit der Rate O (1 / n) abnimmt, sie schließlich unter die von NOOP benötigte Zeit fallen muss. Dies zeigt, dass kein Algorithmus asymptotisch O (1 / n) sein kann, obwohl seine Laufzeit sicherlich bis zu einer Grenze abnehmen kann.
ShreevatsaR
1
Ja ... wie ich bereits an anderer Stelle sagte, sollte jeder Algorithmus, der O (1 / n) ist, für alle Eingaben ebenfalls keine Zeit benötigen. Je nachdem, ob Sie den Null-Algorithmus als 0-mal betrachten oder nicht, gibt es ein O (1) / n) Algorithmus. Also , wenn Sie NOOP betrachten O (1) zu sein, dann gibt es keine O (1 / n) Algorithmen.
ShreevatsaR
7

Ich benutze oft O (1 / n), um Wahrscheinlichkeiten zu beschreiben, die kleiner werden, wenn die Eingaben größer werden - zum Beispiel ist die Wahrscheinlichkeit, dass eine faire Münze bei log2 (n) -Flips auftaucht, O (1 / n).

Dave
quelle
6
Das ist aber nicht das große O. Sie können es nicht einfach neu definieren, um die Frage zu beantworten.
Zifre
11
Es ist keine Neudefinition, es ist genau die Definition von Big O.
ShreevatsaR
10
Ich bin von Beruf theoretischer Informatiker. Es geht um die asymptotische Ordnung einer Funktion.
Dave
4
Big O ist eine Eigenschaft einer beliebigen reellen Funktion. Zeitkomplexität ist nur eine der möglichen Anwendungen. Die Raumkomplexität (die Menge an Arbeitsspeicher, die ein Algorithmus verwendet) ist eine andere. Dass es sich bei der Frage um O (1 / n) -Algorithmen handelt, impliziert, dass es sich um einen dieser Algorithmen handelt (es sei denn, es gibt einen anderen, der für Algorithmen gilt, über die ich nichts weiß). Andere Anwendungen umfassen Ordnungen des Bevölkerungswachstums, z. B. in Conways Leben. Siehe auch en.wikipedia.org/wiki/Big_O_notation
Stewart
5
@ Dave: Die Frage war nicht, ob es O (1 / n) -Funktionen gibt, die offensichtlich existieren. Es ging vielmehr darum, ob es O (1 / n) -Algorithmen gibt, die (mit der möglichen Ausnahme der Nullfunktion) nicht existieren können
Casebash
6

O (1) bedeutet einfach "konstante Zeit".

Wenn Sie einer Schleife [1] einen frühen Exit hinzufügen, verwandeln Sie (in Big-O-Notation) einen O (1) -Algorithmus in O (n), machen ihn aber schneller.

Der Trick ist im Allgemeinen, dass der Algorithmus mit konstanter Zeit der beste ist und linear besser als exponentiell ist, aber für kleine Mengen von n könnte der exponentielle Algorithmus tatsächlich schneller sein.

1: Für dieses Beispiel wird eine statische Listenlänge angenommen

LapTop006
quelle
6

Für alle, die diese Frage lesen und verstehen möchten, worum es in der Unterhaltung geht, könnte dies helfen:

|    |constant |logarithmic |linear|  N-log-N |quadratic|  cubic  |  exponential  |
|  n |  O(1)   | O(log n)   | O(n) |O(n log n)|  O(n^2) |  O(n^3) |     O(2^n)    |
|  1 |       1 |          1 |     1|         1|        1|       1 |             2 |
|  2 |       1 |          1 |     2|         2|        4|       8 |             4 |
|  4 |       1 |          2 |     4|         8|       16|      64 |            16 |
|  8 |       1 |          3 |     8|        24|       64|     512 |           256 |
| 16 |       1 |          4 |    16|        64|      256|   4,096 |         65536 |
| 32 |       1 |          5 |    32|       160|    1,024|  32,768 | 4,294,967,296 |
| 64 |       1 |          6 |    64|       384|    4,069| 262,144 |   1.8 x 10^19 |
Craig O'Connor
quelle
5

Ich glaube, Quantenalgorithmen können mehrere Berechnungen "gleichzeitig" über Überlagerung durchführen ...

Ich bezweifle, dass dies eine nützliche Antwort ist.

Jeff Fleischbällchen Yang
quelle
Das wäre immer noch eine konstante Zeit, dh O (1), was bedeutet, dass für Daten der Größe n dieselbe Zeit benötigt wird wie für Daten der Größe 1.
Freiraum
2
Aber was ist, wenn das Problem ein blasses Bier war? (ah. hah. ha.)
Jeff Meatball Yang
7
Das wäre eine super Position.
Daniel Earwicker
1
Quantenalgorithmen können mehrere Berechnungen durchführen, aber Sie können nur das Ergebnis einer Berechnung abrufen und nicht auswählen, welches Ergebnis Sie erhalten möchten. Zum Glück können Sie auch Operationen an einem Quantenregister als Ganzes ausführen (z. B. QFT), sodass Sie viel wahrscheinlicher etwas finden :)
Gracenotes
2
es ist vielleicht nicht nützlich, aber es hat den Vorteil, wahr zu sein, was es über einige der am höchsten
bewerteten
4

Viele Menschen haben die richtige Antwort erhalten (Nein) Hier ist eine andere Möglichkeit, dies zu beweisen: Um eine Funktion zu haben, müssen Sie die Funktion aufrufen und eine Antwort zurückgeben. Dies dauert eine gewisse konstante Zeit. AUCH WENN der Rest der Verarbeitung für größere Eingaben weniger Zeit in Anspruch nahm, dauert das Ausdrucken der Antwort (von der wir annehmen können, dass es sich um ein einzelnes Bit handelt) mindestens konstant.

Brian Postow
quelle
2

Wenn eine Lösung vorhanden ist, kann diese in konstanter Zeit = sofort vorbereitet und abgerufen werden. Verwenden Sie beispielsweise eine LIFO-Datenstruktur, wenn Sie wissen, dass die Sortierabfrage in umgekehrter Reihenfolge erfolgt. Dann sind die Daten bereits sortiert, vorausgesetzt, das entsprechende Modell (LIFO) wurde ausgewählt.

Larsson
quelle
2

Welche Probleme werden mit wachsender Bevölkerung einfacher? Eine Antwort ist eine Sache wie Bittorrent, bei der die Download-Geschwindigkeit eine inverse Funktion der Anzahl der Knoten ist. Im Gegensatz zu einem Auto, das langsamer wird, je mehr Sie es laden, beschleunigt ein Filesharing-Netzwerk wie Bittorrent die Anzahl der verbundenen Knoten.

Niklas R.
quelle
Ja, aber die Anzahl der Bittorrent-Knoten entspricht eher der Anzahl der Prozessoren in einem Parallelcomputer. Das "N" in diesem Fall entspricht der Größe der Datei, die heruntergeladen werden soll. So wie Sie ein Element in einem unsortierten Array der Länge N in konstanter Zeit finden könnten, wenn Sie N Computer hätten, könnten Sie eine Datei der Größe N in konstanter Zeit herunterladen, wenn Sie N Computer hätten, die versuchen, Ihnen die Daten zu senden.
Kibbee
2

Sie können nicht unter O (1) gehen, jedoch ist O (k), wo k kleiner als N ist, möglich. Wir haben sie sublineare Zeitalgorithmen genannt . Bei einigen Problemen kann der sublineare Zeitalgorithmus nur ungefähre Lösungen für ein bestimmtes Problem liefern. Manchmal ist eine ungefähre Lösung jedoch in Ordnung, wahrscheinlich weil der Datensatz zu groß ist oder weil er viel zu rechenintensiv ist, um alle zu berechnen.

Hao Wooi Lim
quelle
1
Nicht sicher ob ich verstehe. Log (N) ist kleiner als N. Bedeutet das, dass Log (N) ein sublinearer Algorithmus ist? Und es gibt viele Log (N) -Algorithmen. Ein solches Beispiel ist das Finden eines Werts in einem Binärbaum. Diese unterscheiden sich jedoch immer noch von 1 / N, da Log (N) immer zunimmt, während 1 / n eine abnehmende Funktion ist.
Kibbee
In Bezug auf die Definition ist der sublineare Zeitalgorithmus jeder Algorithmus, dessen Zeit langsamer als die Größe N wächst. Dies schließt also den logarithmischen Zeitalgorithmus ein, der Log (N) ist.
Hao Wooi Lim
2
Äh, sublineare Zeitalgorithmen können genaue Antworten geben, z. B. binäre Suche in einem geordneten Array auf einem RAM-Computer.
A. Rex
@EIN. Rex: Hao Wooi Lim sagte "Bei einigen Problemen".
LarsH
1

Was ist damit:

void FindRandomInList(list l)
{
    while(1)
    {
        int rand = Random.next();
        if (l.contains(rand))
            return;
    }
}

Mit zunehmender Größe der Liste nimmt die erwartete Laufzeit des Programms ab.

Shalmanese
quelle
Ich denke, Sie verstehen die Bedeutung von O (n) nicht
Markus Lausberg
Nicht mit Liste, mit Array oder Hash, wo constainsist O (1)
Vava
ok, die Zufallsfunktion kann als Lazy Array betrachtet werden. Sie suchen also im Grunde jedes Element in der "Lazy Random List" und prüfen, ob es in der Eingabeliste enthalten ist. Ich denke, das ist schlimmer als linear, nicht besser.
hasen
Er hat irgendwann einen Punkt, wenn Sie bemerken, dass int nur begrenzte Werte hat. Wenn ich also 2 <sup> 64 </ sup> -Werte enthalten würde, wird es den ganzen Weg augenblicklich sein. Was es sowieso schlimmer macht als O (1) :)
vava
1

O (1 / n) ist nicht kleiner als O (1). Dies bedeutet im Grunde, dass je mehr Daten Sie haben, desto schneller geht der Algorithmus. Angenommen, Sie erhalten ein Array und füllen es immer mit bis zu 10 100 Elementen aus, wenn es weniger enthält, und tun nichts, wenn es mehr gibt. Dieser ist natürlich nicht O (1 / n), sondern so etwas wie O (-n) :) Schade, dass die O-Big-Notation keine negativen Werte zulässt.

Vava
quelle
1
"O (1 / n) ist nicht kleiner als O (1)" - wenn eine Funktion f O (1 / n) ist, ist es auch O (1). Und big-oh fühlt sich sehr nach einer "kleineren als" Beziehung an: Es ist reflexiv, es ist transitiv, und wenn wir Symmetrie zwischen f und g haben, sind die beiden äquivalent, wobei Big-Theta unsere Äquivalenzbeziehung ist. ISTR "echte" Ordnungsbeziehungen, bei denen a <= b und b <= a a = b implizieren müssen, und netcraft ^ W wikipedia bestätigt dies. In gewissem Sinne kann man also sagen, dass O (1 / n) tatsächlich "kleiner als" O (1) ist.
Jonas Kölker
1

Wie bereits erwähnt, kann es abgesehen von der möglichen Ausnahme der Nullfunktion keine geben O(1/n) Funktionen geben, da sich die benötigte Zeit 0 nähern muss.

Natürlich gibt es einige Algorithmen, wie die von Konrad definierten, die weniger als O(1)zumindest in gewissem Sinne sein sollten.

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

Wenn Sie diese Algorithmen untersuchen möchten, sollten Sie entweder Ihre eigene asymptotische Messung oder Ihren eigenen Zeitbegriff definieren. Zum Beispiel könnte ich in dem obigen Algorithmus die Verwendung einer Anzahl von "freien" Operationen eine festgelegte Anzahl von Malen erlauben. Wenn ich im obigen Algorithmus t 'definiere, indem ich die Zeit für alles außer dem Schlaf ausschließe, dann ist t' = 1 / n, was O (1 / n) ist. Es gibt wahrscheinlich bessere Beispiele, da das asymptotische Verhalten trivial ist. Tatsächlich bin ich mir sicher, dass jemand da draußen Sinne finden kann, die nicht triviale Ergebnisse liefern.

Casebash
quelle
1

Die meisten anderen Antworten interpretieren Big-O so, dass es sich ausschließlich um die Laufzeit eines Algorithmus handelt. Da die Frage dies jedoch nicht erwähnte, hielt ich es für erwähnenswert, die andere Anwendung von Big-O in der numerischen Analyse zu erwähnen, bei der es um Fehler geht.

Viele Algorithmen können O (h ^ p) oder O (n ^ {- p}) sein, je nachdem, ob es sich um die Schrittgröße (h) oder die Anzahl der Unterteilungen (n) handelt. Zum Beispiel in Eulers Methode suchen Sie beispielsweise nach einer Schätzung von y (h), vorausgesetzt, Sie kennen y (0) und dy / dx (die Ableitung von y). Ihre Schätzung von y (h) ist genauer, je näher h an 0 liegt. Um also y (x) für ein beliebiges x zu finden, nimmt man das Intervall 0 bis x, teilt es bis zu n Teilen auf und führt die Euler-Methode aus an jedem Punkt, um von y (0) zu y (x / n) zu y (2x / n) zu gelangen, und so weiter.

Die Euler-Methode ist also ein O (h) - oder O (1 / n) -Algorithmus, bei dem h normalerweise als Schrittgröße und n als die Häufigkeit interpretiert wird, mit der Sie ein Intervall teilen.

Aufgrund von Gleitkomma-Rundungsfehlern können Sie in realen numerischen Analyseanwendungen auch O (1 / h) haben . Je kleiner Sie Ihr Intervall machen, desto mehr Stornierungen treten bei der Implementierung bestimmter Algorithmen auf, desto mehr signifikante Ziffern gehen verloren und daher mehr Fehler, die durch den Algorithmus weitergegeben werden.

Wenn Sie für die Euler-Methode Gleitkommazahlen verwenden, verwenden Sie einen ausreichend kleinen Schritt und eine Stornierung, und Sie fügen einer großen Zahl eine kleine Zahl hinzu, wobei die große Zahl unverändert bleibt. Für Algorithmen, die die Ableitung durch Subtrahieren von zwei Zahlen von einer Funktion berechnen, die an zwei sehr engen Positionen ausgewertet wird, wobei y '(x) mit (y (x + h) - y (x) / h) in glatten Funktionen y angenähert wird (x + h) nähert sich y (x), was zu einer großen Aufhebung und einer Schätzung für die Ableitung mit weniger signifikanten Zahlen führt. Dies wird sich wiederum auf jeden Algorithmus übertragen, für den Sie die Ableitung benötigen (z. B. ein Randwertproblem).

Andrew Lei
quelle
0

OK, ich habe ein bisschen darüber nachgedacht, und vielleicht gibt es einen Algorithmus, der dieser allgemeinen Form folgen könnte:

Sie müssen das Problem des Handlungsreisenden für ein Diagramm mit 1000 Knoten berechnen. Sie erhalten jedoch auch eine Liste der Knoten, die Sie nicht besuchen können. Je größer die Liste der nicht sichtbaren Knoten wird, desto leichter lässt sich das Problem lösen.

Shalmanese
quelle
4
Es ist dann eine andere Art von n im O (n). Mit diesem Trick könnte man sagen, dass jeder Algorithmus O (q) hat, wobei q beispielsweise die Anzahl der in China lebenden Menschen ist.
Vava
2
Boyer-Moore ist von ähnlicher Art (O (n / m)), aber das ist nicht wirklich "besser als O (1)", weil n> = m. Ich denke, dasselbe gilt für Ihren "nicht sichtbaren TSP".
Niki
Selbst in diesem Fall ist die Laufzeit des TSP NP-Complete. Sie entfernen einfach Knoten aus dem Diagramm und verringern daher effektiv n.
Ed James
0

Ich sehe einen Algorithmus, der zugegebenermaßen O (1 / n) zu einer Obergrenze gehört:

Sie haben eine große Reihe von Eingaben, die sich aufgrund von etwas außerhalb der Routine ändern (möglicherweise spiegeln sie die Hardware wider oder es könnte sogar ein anderer Kern im Prozessor sein, der dies tut), und Sie müssen einen zufälligen, aber gültigen auswählen.

Wenn es sich nicht ändern würde, würden Sie einfach eine Liste von Elementen erstellen, eine zufällig auswählen und O (1) Zeit erhalten. Die Dynamik der Daten schließt jedoch das Erstellen einer Liste aus. Sie müssen lediglich zufällig prüfen und die Gültigkeit der Prüfung testen. (Und beachten Sie, dass es von Natur aus keine Garantie gibt, dass die Antwort bei der Rückgabe noch gültig ist. Dies könnte immer noch Verwendung haben - beispielsweise die KI für eine Einheit in einem Spiel. Sie könnte auf ein Ziel schießen, das währenddessen außer Sichtweite war den Abzug betätigen.)

Dies hat eine Worst-Case-Leistung von unendlich, aber eine durchschnittliche Fallleistung, die abnimmt, wenn sich der Datenraum füllt.

Loren Pechtel
quelle
0

Bei der numerischen Analyse sollten Approximationsalgorithmen eine subkonstante asymptotische Komplexität in der Approximationstoleranz aufweisen.

class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}
Sam Harwell
quelle
meinst du wirklich subkonstante oder sublinear? Warum sollten Approximationsalgorithmen subkonstant sein? Und was bedeutet das überhaupt?
LarsH
@LarsH, der Fehler von Approximationsalgorithmen ist proportional zur Schrittgröße (oder zu einer positiven Potenz davon). Je kleiner Ihre Schrittgröße ist, desto kleiner ist der Fehler. Eine andere übliche Methode zur Untersuchung eines Approximationsproblems ist der Fehler im Vergleich dazu, wie oft ein Intervall geteilt wird. Die Anzahl der Partitionen eines Intervalls ist umgekehrt proportional zur Schrittgröße, sodass der Fehler umgekehrt proportional zu einer positiven Potenz der Anzahl der Partitionen ist. Wenn Sie die Anzahl der Partitionen erhöhen, nimmt Ihr Fehler ab.
Andrew Lei
@ AndrewLei: Wow, eine Antwort fast 7 Jahre später! Ich verstehe Sams Antwort jetzt besser als damals. Danke für die Antwort.
LarsH
0

Ich denke weniger als O (1) ist nicht möglich. Jede von algo benötigte Zeit wird als O (1) bezeichnet. Aber für O (1 / n) wie wäre es mit der folgenden Funktion. (Ich weiß, dass es in dieser Lösung bereits viele Varianten gibt, aber ich denke, sie haben alle einige Mängel (nicht schwerwiegend, sie erklären das Konzept gut). Hier also eine, nur aus Gründen der Argumentation:

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
  if n <= 0.0:           #If input is actually 0, infinite loop.
    while True:
      sleep(1)           #or pass
    return               #This line is not needed and is unreachable
  delta = 0.0001
  itr = delta
  while delta < C/n:
    itr += delta

Mit zunehmendem n nimmt die Funktion daher immer weniger Zeit in Anspruch. Es wird auch sichergestellt, dass die Funktion für immer zurückkehrt, wenn die Eingabe tatsächlich 0 ist.

Man könnte argumentieren, dass es durch die Präzision der Maschine begrenzt wird. Somit hat es eine Obergrenze, es ist O (1). Aber wir können das auch umgehen, indem wir Eingaben von n und C in Zeichenfolgen vornehmen. Das Hinzufügen und Vergleichen erfolgt über eine Zeichenfolge. Die Idee ist, dass wir damit n beliebig klein reduzieren können. Somit ist die Obergrenze der Funktion nicht begrenzt, selbst wenn wir n = 0 ignorieren.

Ich glaube auch, dass wir nicht einfach sagen können, dass die Laufzeit O (1 / n) ist. Aber wir sollten so etwas wie O sagen (1 + 1 / n)

user1953366
quelle
-1

Es kann möglich sein, einen Algorithmus zu konstruieren, der O (1 / n) ist. Ein Beispiel wäre eine Schleife, die ein Vielfaches von f (n) -n Mal wiederholt, wobei f (n) eine Funktion ist, deren Wert garantiert größer als n ist und die Grenze von f (n) -n, wenn n gegen unendlich geht, ist Null. Die Berechnung von f (n) müsste auch für alle n konstant sein. Ich weiß nicht ohne weiteres, wie f (n) aussehen würde oder welche Anwendung ein solcher Algorithmus haben würde. Meiner Meinung nach könnte jedoch eine solche Funktion existieren, aber der resultierende Algorithmus hätte keinen anderen Zweck, als die Möglichkeit eines Algorithmus mit zu beweisen O (1 / n).

Greg
quelle
Ihre Schleife erfordert eine Prüfung, die mindestens eine konstante Zeit in Anspruch nimmt, sodass der resultierende Algorithmus mindestens die Komplexität O (1) aufweist.
Stefan Reich
-1

Ich weiß nichts über Algorithmen, aber in zufälligen Algorithmen treten Komplexitäten von weniger als O (1) auf. Tatsächlich ist o (1) (wenig o) kleiner als O (1). Diese Art von Komplexität tritt normalerweise in randomisierten Algorithmen auf. Zum Beispiel, wie Sie sagten, wenn die Wahrscheinlichkeit eines Ereignisses in der Größenordnung von 1 / n liegt, bezeichnen sie es mit o (1). Oder wenn sie sagen wollen, dass etwas mit hoher Wahrscheinlichkeit passiert (z. B. 1 - 1 / n), bezeichnen sie es mit 1 - o (1).

A. Mashreghi
quelle
-2

Wenn die Antwort unabhängig von den Eingabedaten gleich ist, haben Sie einen O (0) -Algorithmus.

oder mit anderen Worten - die Antwort ist bekannt, bevor die Eingabedaten gesendet werden - die Funktion könnte optimiert werden - also O (0)

pro
quelle
"Ja wirklich?" Sie müssten immer noch einen Wert zurückgeben, wäre es also nicht immer noch O (1)?
Joachim Sauer
7
Nein, O (0) würde bedeuten, dass für alle Eingaben keine Zeit benötigt wird. O (1) ist konstante Zeit.
Pete Kirkham
-2

Die Big-O-Notation stellt das Worst-Case-Szenario für einen Algorithmus dar, der nicht mit seiner typischen Laufzeit identisch ist. Es ist einfach zu beweisen, dass ein O (1 / n) -Algorithmus ein O (1) -Algorithmus ist. Per Definition ist
O (1 / n) -> T (n) <= 1 / n für alle n> = C> 0
O (1 / n) -> T (n) <= 1 / C, seit 1 / n <= 1 / C für alle n> = C
O (1 / n) -> O (1), da die Big-O-Notation Konstanten ignoriert (dh der Wert von C spielt keine Rolle)

Lawrence Barsanti
quelle
Nein: Die Big O-Notation wird auch verwendet, um über Szenarien für den Durchschnittsfall und die erwartete Zeit (und sogar für den besten Fall) zu sprechen. Der Rest folgt.
Konrad Rudolph
Die 'O'-Notation definiert sicherlich eine Obergrenze (in Bezug auf die algorithmische Komplexität wäre dies der schlimmste Fall). Omega und Theta werden verwendet, um den besten bzw. den besten Fall zu bezeichnen.
Roland Ewald
2
Roland: Das ist ein Missverständnis. Obergrenze ist nicht dasselbe wie Worst-Case, die beiden sind unabhängige Konzepte. Betrachten Sie die erwartete (und durchschnittliche) Laufzeit des hashtable-containsAlgorithmus, die als O (1) bezeichnet werden kann - und der schlechteste Fall kann sehr genau als Theta (n) angegeben werden! Omega und Theta können einfach verwendet werden, um andere Grenzen zu bezeichnen, aber um es noch einmal zu sagen : Sie haben nichts mit dem Durchschnitt oder dem besten Fall zu tun.
Konrad Rudolph
Konrad: Stimmt. Dennoch werden Omega, Theata und O normalerweise verwendet, um Grenzen auszudrücken , und wenn alle möglichen Eingaben berücksichtigt werden, repräsentiert O die Obergrenze usw.
Roland Ewald
1
Die Tatsache, dass O (1 / n) eine Teilmenge von O (1) ist, ist trivial und folgt direkt aus der Definition. Wenn eine Funktion g O (h) ist, dann ist jede Funktion f, die O (g) ist, auch O (h).
Tobias
-2

Nichts ist kleiner als O (1) Die Big-O-Notation impliziert die größte Komplexitätsordnung für einen Algorithmus

Wenn ein Algorithmus eine Laufzeit von n ^ 3 + n ^ 2 + n + 5 hat, dann ist es O (n ^ 3). Die niedrigeren Potenzen spielen hier überhaupt keine Rolle, da n ^> als n -> Inf im Vergleich zu irrelevant ist n ^ 3

Ebenso wie n -> Inf ist O (1 / n) im Vergleich zu O (1) irrelevant, daher ist 3 + O (1 / n) dasselbe wie O (1), wodurch O (1) die kleinstmögliche Berechnung ist Komplexität

user112831
quelle
-2
inline void O0Algorithm() {}
etw
quelle
1
Das wäre ein O (1) -Algorithmus.
Lasse V. Karlsen
2
Das auch, aber der Punkt ist, dass es nicht Ω ist (1). Und warum wurde meine Antwort herabgestuft? Wenn Sie denken, dass ich falsch liege, wie wäre es dann mit einer Erklärung?
Stewart
Ich habe an anderer Stelle gefragt, ob diese Antwort im Grunde genommen richtig ist oder nicht, und sie scheint umstritten zu sein: stackoverflow.com/questions/3209139/…
jyoungdev
Nun, es ist inline, also können Sie es als O (0) betrachten. Alle O (0) -Algorithmen sind jedoch trivial (nichts tun), daher ... keine sehr interessante Antwort.
Stefan Reich
@StefanReich Stimmt, es ist keine sehr interessante Antwort, aber es ist eine Antwort.
Stewart
-2

Hier ist ein einfacher O (1 / n) -Algorithmus. Und es macht sogar etwas Interessantes!

function foo(list input) {
  int m;
  double output;

  m = (1/ input.size) * max_value;  
  output = 0;
  for (int i = 0; i < m; i++)
    output+= random(0,1);

  return output;
}

O (1 / n) ist möglich, da es beschreibt, wie sich die Ausgabe einer Funktion mit zunehmender Größe der Eingabe ändert. Wenn wir die Funktion 1 / n verwenden, um die Anzahl der Befehle zu beschreiben, die eine Funktion ausführt, ist es nicht erforderlich, dass die Funktion für jede Eingabegröße Nullbefehle akzeptiert. Es ist vielmehr so, dass für jede Eingabegröße n oberhalb eines Schwellenwerts die Anzahl der erforderlichen Befehle oben durch eine positive Konstante multipliziert mit 1 / n begrenzt ist. Da es keine tatsächliche Zahl gibt, für die 1 / n 0 ist, und die Konstante positiv ist, gibt es keinen Grund, warum die Funktion gezwungen wäre, 0 oder weniger Anweisungen zu akzeptieren.

Ejspencer
quelle
1
Da O (1 / n) unter die horizontale Linie = 1 fällt und n unendlich erreicht, führt Ihr Code immer noch eine bestimmte Anzahl von Schritten aus. Dieser Algorithmus ist ein O (1) -Algorithmus. Die Big-O-Notation ist eine Funktion aller verschiedenen Teile des Algorithmus und wählt den größten aus. Da die Methode immer einige der Anweisungen ausführt, werden bei jedem Erreichen von n unendlich dieselben Anweisungen jedes Mal ausgeführt, und die Methode wird dann in konstanter Zeit ausgeführt. Zugegeben, es wird nicht viel Zeit sein, aber das ist für die Big-O-Notation nicht relevant.
Lasse V. Karlsen