Notasi Besar Bersarang

Katakanlah saya memiliki grafik $|G|$ dengan $|E|=O(V^2)$ujung-ujungnya. Saya ingin menjalankan BFS$G$ yang memiliki waktu berjalan $O(V+E)$.

Rasanya wajar untuk menulis bahwa waktu berjalan pada grafik ini adalah $O(O(V^2)+V)$ dan kemudian menyederhanakannya $O(V^2)$.

Apakah ada kesulitan untuk menggunakan pintasan "remove-the-nested-O" (tidak hanya dalam kasus ini, tetapi lebih umum)?

Mari saya mulai dengan rekomendasi: perlakukan notasi Landau seperti halnya Anda (harus) memperlakukan pembulatan: jarang, putaran terlambat. Jika Anda tahu sesuatu yang lebih tepat daripada$O(.)$, gunakan sampai Anda selesai dengan semua perhitungan, dan Landauify pada akhirnya.

---

Adapun pertanyaannya, mari gali melalui penyalahgunaan notasi ini¹. Bagaimana kita menafsirkan sesuatu seperti$h \in O(f + O(g))$? Kita harus ganti$O$dengan definisi dari dalam ke luar. Jadi, kita dapatkan

$\qquad \displaystyle \exists g' \in O(g).\, h \in O(f + g')$

lalu

$\qquad \displaystyle \exists g' \in O(g).\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + g'(n))$

yang setara dengan

$\qquad \displaystyle \exists c > 0.\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + cg(n))$.

Tentu saja² $d(f(n) + cg(n)) \leq cd(f(n) + g(n))$, kami melihat bahwa ini setara dengan $h \in O(f + g)$; hilangnya presisi diabaikan oleh$O$ bagaimanapun.

---

Bagaimana dengan kombinasi lain, katakan $h \in O(f + \Omega(g))$? Jika kita mencoba yang sama di sini, kita dapatkan

$\qquad \displaystyle \exists g' \in \Omega(g).\, h \in O(f + g')$.

Tapi ini tautologi: $h$tentu dibatasi di atas oleh sesuatu yang sewenang-wenang besar. Jadi, menggabungkan batas atas dan bawah dengan cara ini tidak berarti.

---

1. $O(.)$dan simbol Landau lainnya memetakan fungsi ke kelas fungsi. Memberinya makan kelas fungsi tidak langsung berarti.
2. Setidaknya jika kita hanya mempertimbangkan fungsi positif, yang dapat kita asumsikan dengan aman ketika berbicara tentang runtimes. Saya tidak yakin ini bekerja secara umum.

Saya hanya ingin menambahkan ini karena saya baru saja menemukannya. Sementara pintasan ini baik-baik saja dengan penambahan dan perkalian (saat tidak mencampur$O$ dengan $\Omega$; lihat jawaban yang diterima), harus diperhatikan saat menggunakan eksponen. Contohnya:

$$O(n^{O(m)}) \not= O(n^m).$$ Dalam contoh ini, $n^{2m}$ Milik kelas satu tetapi bukan kelas kedua.

Menurut definisi, $O(g)$ adalah himpunan dan jika Anda menggunakan notasi ini bersarang, Anda akan memiliki satu set dalam himpunan, yang akan salah.

Definisi O-Notasi

$O(g) = \left \lbrace f|\exists c > 0\exists x_0>0 \forall x > x_0: |f(x)| \leq c *|g(x)|\right \rbrace$

Kesalahan

Anda menggunakan istilah suka $O(O(n)+k)$ di mana k dan n adalah fungsi dan $O(n)$adalah satu set. Tapi apa hasil dari fungsi yang ditambahkan ke set? Itu tidak didefinisikan!

Versi yang benar

Alih-alih menggunakan Sarang Landau-Simbol, Anda dapat melakukan hal berikut: $O(m+k),m \in O(n)$

Di Bagian 9.3 "$O$Manipulasi "dari buku Matematika Beton (Edisi Kedua), Knuth telah mendaftarkan beberapa aturan manipulasi pada$O$-notation (Berikut ini, saya berasumsi bahwa keduanya $f(n)$ dan $g(n)$positif; perhatikan bahwa pemesanan aturan telah diubah).

$$\begin{gather} (1). \quad n^m = O(n^{m'}), \quad m \le m' \\ (3). \quad f(n) = O(f(n)) \\ (5). \quad O(O(f(n))) = O(f(n)) \\ (4). \quad c \cdot O(f(n)) = O(f(n)) \\ (2). \quad O(f(n)) + O(g(n)) = O(f(n) + g(n)) \\ (6). \quad O(f(n)) O(g(n)) = O(f(n) g(n)) = f(n) O(g(n))\\ \end{gather}$$

Dengan (3), Anda dapat membungkus / membuka fungsi $f(n)$dengan notasi-O. Kemudian dengan (5), Anda benar-benar dapat membungkus / membuka (atau disebut, sarang ) secara sewenang-wenang. Menggunakan (4), Anda juga dapat menambah / menghapus faktor perkalian konstan ke / dari$O$.

Kemudian, (2) dan (6) memungkinkan Anda untuk memanipulasi bersarang $O$-Catatan dalam cara yang kompatibel dengan $+$ dan $\times$.