Bagaimana membahas koefisien dalam notasi O besar

Notasi apa yang digunakan untuk membahas koefisien fungsi dalam notasi O besar?

Saya memiliki dua fungsi:

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

Jelas, kedua fungsi adalah $O(x^2)$ , memang $\Theta(x^2)$ , tetapi itu tidak memungkinkan perbandingan lebih jauh dari itu. Bagaimana saya membahas koefisien 7 dan 3. Mengurangi koefisien menjadi 3 tidak mengubah kompleksitas asimptotik tetapi masih membuat perbedaan yang signifikan untuk penggunaan runtime / memori.

Apakah salah mengatakan bahwa $f$ adalah $O(7x^2)$ dan $g$ adalah $O(3x^2)$ ? Apakah ada notasi lain yang mempertimbangkan koefisien? Atau apa cara terbaik untuk membahas ini?

Besar- dan besar- notasi menyembunyikan koefisien jangka terkemuka, jadi jika Anda memiliki dua fungsi yang baik Anda tidak dapat membandingkan nilai absolut mereka tanpa melihat fungsi sendiri. Tidak salah jika mengatakan bahwa , tetapi itu tidak informatif karena juga benar (dan, sebenarnya, ini untuk konstanta positif ).$O$$\Theta$$\Theta(n^2)$$7x^2 + 4x + 2 = \Theta(7x^2)$$7x^2 + 4x + 2 = \Theta(3x^2)$$\Theta(kx^2)$$k$

Ada beberapa notasi lain yang mungkin ingin Anda gunakan. Sebagai contoh, notasi adalah klaim yang jauh lebih kuat daripada big- :$\sim$$\Theta$

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

Misalnya, , tetapi klaim akan salah. Anda dapat menganggap notasi tilde sebagai notasi yang mempertahankan koefisien terkemuka, yang tampaknya menjadi yang Anda cari jika Anda peduli dengan koefisien terkemuka dari istilah pertumbuhan dominan.$7x^2 + 4x + 2 \sim 7x^2$$7x^2 + 4x + 2 \sim 3x^2$$\Theta$

Tilde adalah satu pendekatan. Jika Anda ingin tetap dengan , bisa dibilang$O$

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

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