Mengapa memiliki interpretasi?

Dalam CLRS (pada halaman 49-50), apa arti dari pernyataan berikut:

$\Sigma_{i=1}^{n} O(i)$ hanya merupakan fungsi anonim tunggal (dari ), tetapi tidak sama dengan , yang tidak benar-benar memiliki interpretasi. "$i$$O(1)+O(2)+\cdots+O(n)$

Karena , menggoda untuk menyarankan bahwa ... tetapi ini sebenarnya tidak valid. Alasannya adalah bahwa mungkin ada konstanta yang berbeda untuk setiap istilah dalam jumlah.$1+2+\dots+n =O(n^2)$$O(1)+O(2)+\dots+O(n) = O(n^2)$

Sebuah contoh

Izinkan saya memberi contoh. Pertimbangkan jumlah , , , , dan seterusnya. Perhatikan bahwa , , , , dan seterusnya untuk setiap istilah dalam jumlah. Oleh karena itu, masuk akal untuk menulis dalam bentuk . Jadi bisakah kita menyimpulkan bahwa ? Nggak. Bahkan, , jadi .$S(1) = 1^2$$S(2) = 1^2 + 2^2$$S(3) = 1^2 + 2^2 + 3^2$$S(4) = 1^2 + 2^2 + 3^2 + 4^2$$1^2 \in O(1)$$2^2 \in O(2)$$3^2 \in O(3)$$4^2 \in O(4)$$S(j)=1^2 + \dots + j^2$$S(j) = O(1) + \dots + O(j)$$S(j) = O(j^2)$$S(n) = n(n+1)(2n+1)/6$$S(n) = \Theta(n^3)$

Jika itu tidak membantu, mari kita coba pengembangan matematika berikut yang lebih tepat:

Formalisasi

Ingat bahwa penafsiran, katakanlah, adalah bahwa ia adalah himpunan fungsi non-negatif (yaitu, himpunan fungsi sedemikian sehingga ada konstanta sedemikian rupa sehingga untuk semua ).$O(n^2)$$f(n)$$f(n)$$c \ge 0, d\ge 0$$f(n) \le c \cdot n^2$$n\ge d$

Yang paling dekat dengan interpretasi adalah bahwa ia adalah himpunan fungsi dari bentuk sedemikian rupa sehingga , , ..., .$O(1) + O(2) + \dots + O(n)$$f_1(n) + f_2(n) + \dots + f_n(n)$$f_1(n) \in O(1)$$f_2(n) \in O(2)$$f_n(n) \in O(n)$

Tetapi sekarang konstanta untuk setiap dapat berbeda. Jadi, setiap adalah fungsi non-negatif sedemikian rupa sehingga terdapat konstanta dengan untuk semua .$f_i$$f_i$$f_i$$c_i\ge 0,d_i \ge 0$$f_i(n) \le c_i \cdot i$$n \ge d_i$

Sekarang, mengingat ini, apa yang bisa kita katakan tentang ? Tidak banyak berguna. Kita tahu bahwa ada konstanta sedemikian rupa sehingga untuk semua . Sekarang apa yang bisa kita katakan tentang jumlah ini? Yah, jawabannya adalah kita tidak bisa mengatakan apa-apa sama sekali. Ini bisa menjadi besar secara sewenang-wenang. Sangat menggoda untuk membiarkan dan mengatakan bahwa ... tetapi ini sebenarnya tidak benar, karena kita membutuhkan nilai konstanta tunggal yang bekerja untuk semua , dan nilainya$g(n) = f_1(n) + f_2(n) + \dots + f_n(n)$$d=\max(d_1,d_2,\dots,d_n)$$g(n) \le c_1 \cdot 1 + c_2 \cdot 2 + \dots + c_n \cdot n$$n\ge d$$c=\max(c_1,c_2,\dots,c_n)$$g(n) \le c \cdot (1+2+\dots+n) \le c \cdot n^2 = O(n^2)$$c$$n$$\max(c_1,c_2,\dots,c_n)$ adalah fungsi dari , bukan konstanta.$n$

Jadi mungkin tidak ada konstanta sehingga ; mungkin tidak ada konstanta sehingga . Tidak ada jaminan bahwa .$c$$g(n) \le c \cdot (1+2+\dots+n)$$c$$g(n) \le c \cdot n^2$$g(n) \in O(n^2)$

Untuk lebih banyak membaca

Lihat https://math.stackexchange.com/q/86076/14578 dan jumlah Jumlah Landau ditinjau kembali untuk pertanyaan lain yang berhubungan dengan masalah umum ini.

Alasan bahwa komentar CLRS ini membingungkan adalah bahwa, secara teknis, adalah didefinisikan sebagai . Apa yang sebenarnya terjadi adalah bahwa CLRS menyalahgunakan notasi demi kesederhanaan:$\sum_{i=1}^{n} O(i)$$O(1) + O(2) + \ldots O(n)$

• $O(1)$ mewakili satu set fungsi. Ini termasuk, misalnya, , , dan .$f(n)=1$$f(n)=1/n$$f(n)=n^{1/n}$
• Saat Anda menulis Anda secara teknis menambahkan dua set dan dengan operasi penjumlahan . Ketika ini dilakukan dengan lebih dari jumlah istilah yang konstan, itu dapat menyebabkan perilaku yang tidak terduga, seperti DW jelas menjelaskan dalam jawaban lain.$O(1) + O(2)$$O(1)$$O(2)$

Alih-alih, CLRS ingin Anda menafsirkan sebagai mana fungsi generik . Sebagai contoh, mereka akan menulis bahwa adalah , atau .$\sum_{i=1}^n O(i)$$\sum_{i=1}^n f(i)$$f(i) \in O(i)$$\sum_{i=1}^n 3i-5$$\sum_{i=1}^n O(i)$$O(n^2)$