Das ist mir ohne besonderen Grund in den Sinn gekommen, und ich nehme an, es ist eine seltsame Frage. Gibt es bekannte Algorithmen oder Probleme, die einfacher oder schneller gelöst werden können? 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 Inputs gibt, die es leicht machen, etwas zu entscheiden, aber ich kann mir nicht vorstellen, was.
Wenn es keine negative Komplexität gibt, gibt es einen Beweis dafür, dass es keine sein kann? Oder hat es nur niemand gefunden?
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 Definitionsteil des wikipedia Artikels 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 pro formale Definition.
Kurze Antwort: Es ist nicht möglich, weil die Definition dies sagt.
aktualisieren Um es klar zu stellen, beantworte ich diesen Teil der Frage: Gibt es bekannte Algorithmen oder Probleme, die mit größeren Eingaben leichter oder schneller gelöst werden können?
Wie in der angenommenen Antwort hier erwähnt, gibt es no Algorithmen, die bei größeren Eingaben schneller arbeiten.
Gibt es O (1 / n) -Algorithmen?
Selbst ein Algorithmus wie sleep(1/n) muss Zeit damit verbringen, seine Eingabe zu lesen, so dass seine Laufzeit eine untere Grenze hat.
Insbesondere verweist der Autor auf einen relativ einfachen Teilstringsuchalgorithmus:
Ссылка
PS Aber der Begriff "negative Komplexität" für solche Algorithmen scheint mir nicht vernünftig zu sein.
In einem Algorithmus zu denken, der in einer negativen Zeit ausgeführt wird, ist dasselbe 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 zum mathematischen Teil:
Wenn Sie nicht mit einer Abfolge von Aktionen kommen können, die zeitlich rückwärts laufen (Sie wissen nie ... lol) , ist der Beweis ganz einfach:
positiveZeit = O (-1) bedeutet:
positive Zeit & lt; = c * -1, für jedes C & gt; 0 und n & gt; n0 & gt; 0
Betrachten Sie die Einschränkung "C & gt; 0". Wir können keine positive Zahl finden, die mit -1 multipliziert wird und eine weitere positive Zahl ergibt. Wenn man das berücksichtigt, ist dies das Ergebnis:
positiveTime & lt; = negativeNummer, für jedes n & gt; n0 & gt; 0
Was nur beweist, dass Sie keinen Algorithmus mit O (-1) haben können.
Nicht wirklich. O (1) ist das Beste, auf das du hoffen kannst.
Das, was mir am nächsten kommt, ist die Sprachübersetzung, bei der große Datensätze von Ausdrücken in der Zielsprache verwendet werden, um kleinere Auszüge 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).
Nun, für viele Berechnungen wie "gegebene Eingabe A return f (A)" können Sie Berechnungsergebnisse "cachen" (speichern Sie sie in Array oder Karte), die Berechnung schneller mit größerer Anzahl von Werten, wenn einige von denen Werte wiederholen.
Aber ich glaube nicht, dass es sich um "negative Komplexität" handelt. 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 Daten zu sein sortiert.
Ich denke, um eine negative Komplexität zu haben, sollte der Algorithmus das Ergebnis zurückgeben, bevor er aufgefordert wurde, das Ergebnis zu berechnen. I.e. es sollte mit einer Zeitmaschine verbunden sein und mit dem "Großvater-Paradox" umgehen können.
Wie bei der anderen Frage nach dem 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 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) eine O (1 / n) Zeit benötigt, könnte für eine Eingangsgröße von 1 Byte bis 1 Gigabyte sehr sinnvoll sein. 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).
Ich weiß nicht, ob das passt, aber es erinnert mich an Bittorrent. Je mehr Leute eine Datei herunterladen, desto schneller geht es für sie alle
Tags und Links algorithm complexity-theory big-o