Wie man Koeffizienten in Big-O-Notation diskutiert

Welche Notation wird verwendet, um die Funktionskoeffizienten in der Big-O-Notation zu diskutieren?

Ich habe zwei Funktionen:

$f(x) = 7x^2 + 4x +2$
$g(x) = 3x^2 + 5x +4$

Offensichtlich sind beide Funktionen , tatsächlich , aber das erlaubt keinen weiteren Vergleich. Wie diskutiere ich die Koeffizienten 7 und 3. Das Reduzieren des Koeffizienten auf 3 ändert nichts an der asymptotischen Komplexität, macht aber dennoch einen signifikanten Unterschied für die Laufzeit- / Speichernutzung. $O(x^2)$ $\Theta(x^2)$

Ist es falsch zu sagen , dass ist und ist ? Gibt es eine andere Notation, die Koeffizienten berücksichtigt? Oder wie könnte man das am besten diskutieren? $f$ $O(7x^2)$ $g$ $O(3x^2)$

terminology asymptotics landau-notation Raphael
quelle

Es ist nicht falsch, es ist nur redundant, weil .

O (7 x^{2}) = O (x^{2})

$O(7 x^2) = O(x^2)$

Siehe auch unsere Referenzfrage .

Raphael

Antworten:

Big- und Big- Notationen verbergen die Koeffizienten des führenden Terms. Wenn Sie also zwei Funktionen haben, die beide , können Sie ihre absoluten Werte nicht vergleichen, ohne die Funktionen selbst zu betrachten. Es ist an sich nicht falsch zu sagen, dass , aber es ist nicht informativ, weil auch wahr ist (und,) Tatsächlich ist es für jede positive Konstante ). $O$ $\Theta$ $\Theta(n^2)$ $7x^2 + 4x + 2 = \Theta(7x^2)$ $7x^2 + 4x + 2 = \Theta(3x^2)$ $\Theta(kx^2)$ $k$

Es gibt andere Notationen, die Sie stattdessen verwenden möchten. Zum Beispiel ist die Notation eine viel stärkere Behauptung als big- : $\sim$ $\Theta$

$\qquad \displaystyle f(x) \sim g(x) \iff \lim_{x \to \infty} \frac{f(x)}{g(x)} = 1$

Zum Beispiel , aber die Behauptung wäre falsch. Sie können sich die Tilde-Notation als Notation , bei der die führenden Koeffizienten erhalten bleiben. Dies scheint das zu sein, wonach Sie suchen, wenn Sie sich für den führenden Koeffizienten des dominanten Wachstumsterms interessieren. $7x^2 + 4x + 2 \sim 7x^2$ $7x^2 + 4x + 2 \sim 3x^2$ $\Theta$

templatetypedef
quelle

Tilde Notation ist das, wonach ich suche. Ich war mir sicher, dass es etwas gab, an das ich mich einfach nicht erinnern konnte, und Suchanfragen erwiesen sich als erfolglos. Vielen Dank!

Die Tilde ist ein Ansatz. Wenn du bei bleiben willst , könntest du sagen $O$

$\qquad f(x) = 7x^2 + O(x)$ und

$\qquad g(x) = 3x^2 + O(x)$ .

Raphael
quelle

Noch besser: Sagen Sie f (x) = 7x ^ 2 + o (x ^ 2) und verwenden Sie die Little-o-Notation, um zu verdeutlichen, dass das, was übrig bleibt, asymptotisch kleiner als x ^ 2 ist.

Templatetypedef

O (x) ist streng kleiner als o (x ^ 2), daher wäre die Verwendung weniger klar als die Verwendung von Big-O. Auf der anderen Seite ist die Verwendung von little-o definitiv häufiger, wenn Sie sagen möchten, dass Sie das richtige erste Semester haben, weil Sie sich dann nicht um das nächste Semester kümmern müssen. (Und wenn wir völlig klar sein wollen, müssen wir erklären, warum wir nicht einfach 7x ^ 2 + 4x + 2

Du hast absolut Recht ... ich entschuldige mich!

Templatetypedef

Beachten Sie, dass die strenge Schreibweise " mit " wäre. In jedem Fall ist dies sehr nützlich, wenn Sie mehr als die "erste" Konstante festlegen möchten. Sie können " " sagen, was Sie mit nicht tun können .

f (x) = 7 x^{2} + g (x)

$f(x) = 7x^2 + g(x)$

g (x) \in O (x)

$g(x) \in O(x)$

f (x) = 7 x^{2} + 4 x + O (1)

$f(x) = 7x^2 + 4x + O(1)$

\sim

$\sim$

Raphael