Nehmen wir an, Sie haben einen Algorithmus entworfen, von dem Sie denken, dass er in O (n) läuft. Wenn ich die Zeit mißt, läuft es mit 1000 Input und erhöht dann den Input 10x und messe dann wieder. Kann ich folgern, dass O (n) korrekt ist, wenn die Laufzeit fast 10 Mal höher ist als der erste Versuch?
Wie dumm wäre das? Offensichtlich würde die Wiederholung des Tests eine bessere Genauigkeit ergeben, aber ich möchte wissen, ob das überhaupt Sinn macht.
Oft lautet die Antwort "ja". Wenn Sie die Problemgröße um 10 erhöhen und die Zeit um 10 steigt, haben Sie wahrscheinlich richtigerweise O (N) angenommen. Allerdings ist die Anzahl eher nicht so schön.
Wenn Sie von 1.000 auf 10.000 gehen, steigt ein O (N.logN) -Algorithmus ungefähr um den Faktor 13 (siehe bc unten). Das ist nicht weit weg von 10, und Sie könnten fälschlicherweise denken, dass ein Anstieg von 12 O (N.logN) und nicht O (N) anzeigt. Wenn Sie jedoch um 10 erhöhen und die Zeit um etwa 100 steigt, handelt es sich wahrscheinlich um einen nichtlinearen Algorithmus - wahrscheinlich O (N 2 ). Also, 2 Punkte sind nicht genug, aber es ist indikativ. Mehrere Läufe und mehr Datenpunkte helfen beide.
Manchmal tritt jedoch etwas anderes ein. Zum Beispiel könnten Sie plötzlich so viel Speicher verwenden, dass Ihr Programm ausgelagert wird, anstatt nur zu laufen. Es wird sich dramatisch verlangsamen, obwohl der Algorithmus bei genügend Ressourcen immer noch linear ist.
Achten Sie auch auf Caching-Effekte und Optimierungseffekte. Caching kann Dinge schneller erscheinen lassen. Wenn der Optimierer zu dem Schluss kommt, dass die Berechnung ignoriert wird, kann die gesamte Berechnung eliminiert werden. Du musst also vorsichtig sein.
Aber mit ein bisschen Glück können Sie das Problem ein paar Größenordnungen (oder zumindest ein paar verschiedene Zahlen) skalieren und eine vernünftige Schätzung treffen, ob es linear oder etwas anderes ist / p>
Im Gegensatz zu der anderen Antwort werde ich "Nein" sagen. Sie können jedoch eine ziemlich gute Schätzung erhalten (nicht einmal eine Schätzung, da es hier nicht angemessen ist). Dies ist wahrscheinlich mit "oft" gemeint.
Die Sache ist, dass Sie nie die konstanten Faktoren kennen. Big Oh ist asymptomatisches Verhalten (im Unendlichen), das ist sehr sehr nützlich, um alles außer dem am meisten wachsenden Begriff fallen zu lassen. Mathematisch können Sie Ihre Annahme nicht bestätigen.
Erstens gibt es hier viele Algorithmen und Anwendungsfälle, in denen asymptomatisches Verhalten in realen Anwendungen nicht sinnvoll ist. Ganz einfach, weil die Eingabeverteilung "typischer Anwendungsfall" abfällt. Dies ist häufiger der Fall. Und Sie könnten es immer noch testen / schätzen.
Aber es gibt auch einen Fall, in dem der beste Algorithmus so große konstante Faktoren hat, dass er auf modernen Systemen nicht anwendbar ist. Das beste Beispiel, das ich kenne, sind große Multiplikationsalgorithmen .
Es gibt jedoch Systeme, die die Komplexitätsklasse eines Algorithmus annähern (besser gesagt). Ich bin mir nicht sicher, ob Codilität es messen oder ihre Schätzung durch Code-Analyse erhalten, aber sie können es tun: Ссылка .
Man kann einen Algorithmus ausführen und die Eingabegröße ändern, Tests ausführen und die Daten an das Modell anpassen. Es ist ganz einfach. Dann können Sie sagen, dass sich der Algorithmus für den getesteten Eingabebereich wie folgt verhält: O(class(n)) . (Dies könnte eine praktische Bedeutung haben, die sogar mehr wert ist als die theoretische asymptotische Komplexität.)
Beachten Sie, dass die Auswahl der Testpunkte nicht trivial ist. Wenn sich Ihr Algorithmus "schnell" verhält, müssen Sie die Eingabegröße auf die nächste Klasse erhöhen. Z.B. Wenn Sie etwas wie (100n+n!) haben, können Sie n={1,10,100} aufrufen, weil es kill Ausführungszeit ist. Allerdings wird n={1,2,3,4,5,6,7} nicht den n! Teil übernehmen (ok 7! ist 5040 , aber für n^2 wäre es viel schwieriger).
Unterm Strich ist es sicherlich möglich, eine gute Schätzung zu erhalten, aber abgesehen von den meisten einfachen Fällen kann es schwierig und schwierig sein, und leider ist es ziemlich schwer zu sagen, ob der Fall schwierig ist oder nicht.
Auch diese Diskussion ist rein theoretisch und überspringt Hardware-Effekte. Ich habe von Algorithmen gehört, die sich n^2 besser verhielten als n^log n , weil früher immer (sehr) cachefreundlich war, aber nehmen Sie mein Wort dafür nicht, ich kann mich nicht an Quelle erinnern.
Die Eingabe der Eingabegröße gegen die Laufzeit für aktuelle Programme ist ein äußerst hilfreiches Werkzeug, mit dem Sie sehen können, wie Ihr Code tatsächlich funktioniert. Im Allgemeinen ist es gefährlich zu denken, dass Sie damit Komplexität ableiten können.
Hier ist ein praktisches Beispiel, wie es zusammenbricht.
Gute Quick-Sort-Implementierungen schwenken das Array in drei Teile: weniger als der Drehpunkt, gleich dem Drehpunkt und größer als der Drehpunkt. Das bedeutet, dass das schnelle Sortieren eines 64-Bit-Zufallsarrays (tatsächlich das Sortieren eines zufälligen Arrays eines beliebigen Datentyps mit fester Größe) O (n) -Vergleiche erfordert, weil schließlich jedes Unterarray konstant ist.
Leider können Sie dies nicht empirisch sehen: Wenn Sie n gegen die Anzahl der Vergleiche plotten, sieht das Diagramm wie n * log (n) aus, bis das Eingabearray viel größer als 2 ^ 64 Elemente wird. Selbst wenn Sie genügend Speicher hatten, erlaubt es Ihre Programmiersprache wahrscheinlich nicht, Arrays dieser Größe zu indizieren.
Dieses Beispiel zeigt auch, dass empirische Messungen Ihnen interessante Daten liefern (dass der Code wie n * log (n) am tatsächlichen Input funktioniert), und Komplexität gibt Ihnen eine theoretische, aber praktisch nutzlose Tatsache, dass asymptotisches Wachstum linear ist.
> Zusätzlich zu dem, was andere gesagt haben. Manchmal können der durchschnittliche Fall und der ungünstigste Fall unterschiedlich sein, und der schlimmste Fall kann schwer zu finden sein. Ein bekanntes Beispiel ist quicksort , mit seinem O(n log n) -Verhaltensverhalten (Missbrauch der O -Notation?) Und O(n^2) Worst-Case-Verhalten. Wenn Sie einen "Black-Box" -Algorithmus (gut, Programm) erhalten haben, können solche schlimmsten Fälle experimentell schwer zu verstehen sein, ohne das Wissen über den Algorithmus.