Warum verwendet Big-O Notation O (1) anstelle von O (k)?
Wenn ich die Big-O-Notation richtig verstehe, sollte k eine konstante Zeit für die Effizienz eines Algorithmus sein. Warum sollte eine konstante Zeit als O(1) und nicht als O(k) betrachtet werden, wenn man bedenkt, dass es eine variable Zeit braucht? Lineares Wachstum ( O(n + k) ) verwendet diese Variable, um die Zeit um eine bestimmte Zeit zu verschieben, warum also nicht das Gleiche für konstante Komplexität?
1 Antwort
Es gibt kein solches lineares Wachstum asymptotisch O(n + k) wobei k eine Konstante ist. Wenn k eine Konstante wäre und Sie zur Grenzdarstellung der algorithmischen Wachstumsraten zurückkehren würden, würden Sie O(n + k) = O(n) sehen, weil Konstanten in Grenzen fallen.
Ihre Antwort lautet möglicherweise O(n + k) aufgrund einer -Variablen k , die grundsätzlich unabhängig vom anderen Eingabesatz n ist. Sie sehen dies häufig in Vergleichen mit Verschiebungen in der Sortieralgorithmusanalyse.
Um zu versuchen, Ihre Frage zu beantworten, warum wir k in der Big-O-Notation ablegen (was meiner Meinung nach schlecht gelehrt wird, was zu all dieser Verwirrung führt), ist eine Definition (wie ich mich erinnere) von O () wie folgt :
Versuchen wir, es hier auf unser Problem anzuwenden, wobei k eine Konstante und somit f (x) = k und g (x) = 1 ist.
- Gibt es
dundn_0, die existieren, um diese Anforderungen zu erfüllen?
Trivialerweise ist die Antwort natürlich ja. Wählen Sie d & gt; k und für n & gt; 0, die Definition gilt.
Tags und Links algorithm complexity-theory notation big-o