Sind bei kleinen Eingangsgrößen Konstanten wichtig? Wie?

Question

Ich ging durch einige Vorträge auf Zeit Komplexität & auf diesem Link https://www.youtube.com/watch?v=__vX2sjlpXU Autor erklärt um 4:50, dass Konstanten in vielen Situationen wichtig sind, wenn sie kleine Eingabegrößen haben. Mit freundlicher

erklären

Answer 1

ist es mit der tatsächlichen Komplexität von 100n und 2n , sie sind also O (n) und O (n) sind zwei Algorithmen Lassen Sie sagen. Für n = 2 benötigen sie 200 bzw. 8 CPU-Zyklen für die Ausführung. Aber für Werte von n mehr als 50 wird der Algorithmus 100n immer besser als 2n Algorithmus.

Auf diese Weise sehen wir, dass Big O für kleinere Eingaben keine gute Beurteilung von Algorithmen ist und dass Konstanten eine wichtige Rolle spielen, besonders wenn sie im Vergleich zur Eingabe ziemlich groß sind.

---

In ähnlicher Weise können Sie das Ergebnis verstehen, wenn mit der Zeit Komplexitäten von 100 + n und 2 + n wie Fällen. Für Werte von n, die nicht groß genug sind, um die Einflüsse der Konstanten zu überholen, können die tatsächlichen Ausführungszeiten letztendlich von den Konstanten anstelle des Eingabewerts n bestimmt werden.

Answer 2

Für den mathematischen Begriff der Zeitkomplexität es spielt nicht Rolle.

Wenn Sie jedoch große Konstanten haben, könnte Ihr Programm, selbst wenn es eine gute Komplexität hat, langsamer sein als ein Programm mit schlechter Komplexität. Was ist offensichtlich, stellen Sie sich einen Schlaf für 1 hour vor, Ihr Programm braucht lange, eine große Konstante. Aber seine Komplexitätsklasse könnte gut sein, da Konstante keine Rolle spielt.

Warum sind sie nicht wichtig? Denn für jedes Programm mit einer schlechteren Komplexität gibt es eine Eingabe (große Eingaben), für die sie irgendwann langsamer werden. Hier

---

ist ein Beispiel:

Gute Komplexität O(1), langsam sowieso:

void method() { 
    sleep(60 * 60 * 1_000); // 1 hour 
} 

Schlimmer Komplexität O(n), schneller für kleine Eingänge:

void method(int n) { 
    for (int i = 0; i < n; i++) { 
     sleep(1_000); // 1 second 
    } 
} 

Allerdings, wenn Sie Eingabe n > 60 * 60 Die zweite Methode wird langsamer .

---

Sie nicht Zeitkomplexität mit den tatsächlichen messbaren Laufzeit, es ist ein großer Unterschied verwechseln sollten.

Zeitkomplexität ist über asymptotisch Grenzen, siehe Definition für f in O(g):

Answer 3

Nun, wenn ich über Algorithmus studiert und ihre Komplexität, unser Professor kurz erklärt, dass Konstanten Rolle ein Menge. In der Komplexitätstheorie gibt es zwei Hauptnotationen, um Komplexität zu erklären. Der erste ist BigO und der zweite ist Tild-Notation.

Angenommen, Sie implementieren eine Prioritätswarteschlange (mit Heap), die 2lgN vergleicht zum Entfernen eines maximalen Elements und 1 + logN zum Einfügen für jedes Element. Nun, was Leute tatsächlich tun, dass sie 2logN entfernen und es als O(logN) schreiben, aber das ist nicht richtig, weil 1+logN nur zum Einfügen eines Elements erforderlich war und wenn Sie ein Element entfernen, dann müssen Sie die Warteschlange (Sinken und schwimmen) Funktionen neu zu balancieren.

Wenn Sie ~2logN als O(logN) schreiben, bedeutet das, dass Sie nur die Komplexität einer Funktion zählen, entweder schwimmen oder sinken.

Als Referenz werde ich hinzufügen, dass an einigen Top-Universitäten, meist Professoren verwenden ~ Notation.

BigO kann schädlich sein. Ein Buch geschrieben von Robert sedgewick and Kevin Wayne verwendet ~ und erklärt auch, warum er das bevorzugt.