Gibt es so etwas wie "negative" Groß-O-Komplexität?

Question

Mögliche Duplizieren:
Are there any O(1/n) algorithms?

Dies ist nur in meinem Kopf auftauchte ohne besonderen Grund, und ich nehme an, es eine seltsame Frage ist. Gibt es bekannte Algorithmen oder Probleme, die einfacher oder schneller mit größerem Eingang lösen? Ich vermute, wenn es solche Dinge gäbe, wäre es nicht für Dinge wie Mutationen oder Sortieren, sondern für Entscheidungsprobleme. Vielleicht gibt es ein Problem, bei dem es eine Menge Input gibt, die es leicht macht, etwas zu entscheiden, aber ich kann mir nicht vorstellen, was.

Wenn es so etwas wie negative Komplexität nicht gibt, gibt es einen Beweis, dass es nicht sein kann? Oder hat es nur noch niemand gefunden?

Answer 1

Nein, das ist nicht möglich. Da Big-Oh eine Annäherung an die Anzahl der Operationen sein soll, die ein Algorithmus in Bezug auf seine Domain-Größe durchführt, wäre es nicht sinnvoll, einen Algorithmus so zu beschreiben, dass er eine negative Anzahl von Operationen verwendet.

Der formale Definitionsabschnitt der Wikipedia article definiert die Big-Oh-Notation tatsächlich in Bezug auf die Verwendung positiver reeller Zahlen. Es gibt also nicht einmal einen Beweis, denn das ganze Konzept von Big-Oh hat keine Bedeutung für die negativen reellen Zahlen nach der formalen Definition.

Kurze Antwort: Es ist nicht möglich, weil die Definition so sagt.

Answer 2

Nicht wirklich. O (1) ist das Beste, auf das du hoffen kannst.

Das nächste, was mir einfällt, ist die Sprachübersetzung, die große Datensätze von Phrasen in der Zielsprache verwendet, um kleinere Ausschnitte aus der Ausgangssprache zu vergleichen. Je größer der Datensatz ist, desto besser (und in gewissem Maße schneller) ist die Übersetzung. Aber das ist immer noch nicht einmal O (1).

Answer 3

Update Nur um klarzustellen, ich bin der Beantwortung dieser Teil der Frage: Gibt es irgendwelche bekannten Algorithmen oder Probleme, die tatsächlich einfacher oder schneller mit größeren Eingang zu lösen?

Wie hier in akzeptierter Antwort erwähnt, gibt es keine Algorithmen mit größerem Eingang schneller arbeiten. Are there any O(1/n) algorithms? Sogar ein Algorithmus wie sleep(1/n) muss Zeit mit dem Lesen seiner Eingabe verbringen, so dass seine Laufzeit eine untere Grenze hat.

Insbesondere Autor referes relativ einfache Teilzeichenfolge Suchalgorithmus:
http://en.wikipedia.org/wiki/Horspool

PS Aber mit Begriff ‚negative Komplexität‘ für solche Algorithmen nicht scheint mich vernünftig zu sein.

Answer 4

Nun, für viele Berechnungen wie "gegebene Eingabe A zurück f (A)" können Sie Berechnungsergebnisse "cachen" (speichern sie in Array oder Karte), die Berechnung schneller mit größerer Anzahl von Werten, wenn einige von diese Werte wiederholen sich.

Aber ich glaube nicht, dass es als "negative Komplexität" qualifiziert. In diesem Fall wird die schnellste Leistung wahrscheinlich als O (1) gezählt, die Worst-Case-Leistung ist O (N), und die durchschnittliche Leistung liegt irgendwo dazwischen.

Dies ist etwas anwendbar für Sortieralgorithmen - einige von ihnen haben O (N) Best-Case-Szenario Komplexität und O (N^2) Worst-Case-Komplexität, abhängig vom Zustand der zu sortierenden Daten.

Ich denke, dass, um negative Komplexität zu haben, Algorithmus sollte Ergebnis zurückgeben, bevor es aufgefordert wurde, das Ergebnis zu berechnen. I.e. es sollte an eine Zeitmaschine angeschlossen sein und sollte mit entsprechenden "grandfather paradox" umgehen können.

Answer 5

In einem Algorithmus zu denken, der in einer negativen Zeit ausgeführt wird, ist das gleiche wie zu denken, dass die Zeit rückwärts geht.

Wenn das Programm um 10:30 Uhr startet und um 10:00 Uhr stoppt, ohne 11:00 Uhr zu passieren, wurde es gerade mit der Zeit = O (-1) ausgeführt.

=]

Nun, für den mathematischen Teil:

Wenn Sie nicht mit einer Reihe von Maßnahmen kommen können, die in der Zeit rückwärts ausführen (man weiß ja nie ... lol), der Beweis ist ganz einfach:

positiveTime = O (-1) bedeutet:

positiveTime < = c * -1, für jede C> 0 und n> n0> 0

Betrachten Sie die Einschränkung "C> 0". Wir können keine positive Zahl finden, die mit -1 multipliziert wird und eine weitere positive Zahl ergibt. Damit in Berücksichtigung, ist dies das Ergebnis:

positiveTime < = negativeNumber, für alle n> n0> 0

Wich beweist nur, dass Sie nicht einen Algorithmus mit O (-1) haben kann.

Answer 6

Wie bei der anderen Frage zum leeren Algorithmus ist diese Frage eher eine Frage der Definition als eine Frage dessen, was möglich oder unmöglich ist. Es ist sicherlich möglich, an ein Kostenmodell zu denken, für das ein Algorithmus O (1/n) Zeit benötigt. (Das ist natürlich nicht negativ, sondern nimmt mit zunehmender Eingabe ab.) Der Algorithmus kann so etwas wie sleep(1/n) als eine der anderen vorgeschlagenen Antworten machen. Es ist wahr, dass das Kostenmodell zusammenbricht, wenn n ins Unendliche gesendet wird, aber n wird niemals ins Unendliche gesendet; Jedes Kostenmodell bricht schließlich zusammen. Zu sagen, dass sleep(1/n) O (1/n) Zeit braucht, könnte sehr sinnvoll für eine Eingangsgröße sein, die von 1 Byte bis 1 Gigabyte reicht. Das ist eine sehr breite Palette für jede Zeit, die Komplexitätsformel anwendbar ist.

Auf der anderen Seite verwendet die einfachste Standarddefinition der Zeitkomplexität Einheitszeitschritte. Es ist unmöglich für eine positive, ganzzahlige Funktion, abnehmende Asymptotiken zu haben; das kleinste, was es sein kann, ist O (1).

Answer 7

Ich weiß nicht, ob das passt, aber es erinnert mich an Bittorrent. Je mehr Leute eine Datei herunterladen, desto schneller geht es für alle von ihnen