Jak omawiać współczynniki w notacji big-O

Jakiej notacji używa się do omawiania współczynników funkcji w notacji big-O?

Mam dwie funkcje:

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

Oczywiście obie funkcje to , a właściwie Θ ( x 2 ) , ale to nie pozwala na dalsze porównania. Jak omówić współczynniki 7 i 3. Zmniejszenie współczynnika do 3 nie zmienia asymptotycznej złożoności, ale nadal robi znaczącą różnicę w użyciu środowiska wykonawczego / pamięci.$O(x^2)$$\Theta(x^2)$

Czy błędem jest stwierdzenie, że oznacza O ( 7 x 2 ), a g oznacza O ( 3 x 2 ) ? Czy istnieje inna notacja uwzględniająca współczynniki? Lub jaki byłby najlepszy sposób na omówienie tego?$f$$O(7x^2)$$g$$O(3x^2)$

Big- i big- Θ notacje ukryć współczynniki wiodących perspektywie, więc jeśli masz dwie funkcje, które są zarówno Θ ( n 2 ) nie można porównywać ich wartości bezwzględne, nie patrząc na same funkcje. Nie jest błędem samo w sobie twierdzenie, że 7 x 2 + 4 x + 2 = not ( 7 x 2 ) , ale nie jest to pouczające, ponieważ 7 x 2 + 4 x + 2 = Θ ( 3 x 2$O$$\Theta$$\Theta(n^2)$$7x^2 + 4x + 2 = \Theta(7x^2)$$7x^2 + 4x + 2 = \Theta(3x^2)$jest również prawdziwe (i w rzeczywistości jest to dla dowolnej dodatniej stałej k ).$\Theta(kx^2)$$k$

Istnieją inne notacje, których możesz użyć zamiast tego. Na przykład notacja jest znacznie silniejszym twierdzeniem niż duże Θ :$\sim$$\Theta$

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

Na przykład , ale twierdzenie 7 x 2 + 4 x + 2 ∼ 3 x 2 byłoby fałszywe. Można myśleć o tyldy notacji jako Θ notacji że zachowuje prowadzące współczynniki, co wydaje się być to, czego szukasz, jeśli nie dba o wiodącej współczynnika dominującej perspektywie wzrostu.$7x^2 + 4x + 2 \sim 7x^2$$7x^2 + 4x + 2 \sim 3x^2$$\Theta$

Tylda to jedno podejście. Jeśli chcesz trzymać się , możesz powiedzieć$O$

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

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