Rantai tak terbatas besar

Pertama, izinkan saya menulis definisi big $O$ hanya untuk membuat semuanya eksplisit.

$f(n)\in O(g(n))\iff \exists c, n_0\gt 0$ sehingga$0\le f(n)\le cg(n), \forall n\ge n_0$

Katakanlah kita memiliki sejumlah fungsi terbatas: $f_1,f_2,\dots f_n$ memuaskan:

$O(f_1)\subseteq O(f_2)\dots \subseteq O(f_n)$

Dengan transitivitas $O$ , kita memiliki itu: $O(f_1)\subseteq O(f_n)$

Apakah terus ini jika kita memiliki rantai tak terbatas $O's$ ? Dengan kata lain, apakah $O(f_1) \subseteq O(f_\infty)$ ?

Saya kesulitan membayangkan apa yang terjadi.

Pertama-tama kita perlu mengklarifikasi apa yang kita maksud dengan "apakah ini berlaku jika kita memiliki rantai tak terbatas?". Kami menafsirkannya sebagai urutan fungsi tak terbatas sedemikian rupa sehingga untuk semua i kita memiliki f i ( n ) = O ( f i + 1 ( n ) ) . Urutan seperti itu mungkin tidak memiliki fungsi terakhir.$\{f_i:\mathbb{N}\to\mathbb{N} \mid 1\leq i\}$$i$$f_i(n) = O(f_{i+1}(n))$

$f_\infty(n) = \lim_{i\to \infty} f_i(n)$$f_1(n) = O(f_\infty(n))$$f_i(n) = \frac{n}{i}$$i$$f_i(n)=\Theta(n)$$f_i(n) = O(f_{i+1}(n))$$f_\infty(n)=\lim_{i\to\infty}f_i(n)=0=\Theta(1)$$f_1(n) \neq O(f_\infty(n))$

Di sisi lain kita dapat melihat batas urutan kelas yang tidak perlu sama dengan kelas batas fungsi . Kami memiliki , oleh karena itu dan untuk semua . Batas atasan berisi semua elemen (fungsi dalam kasus ini) yang sering terjadi tanpa batas dan batas inferior berisi semua elemen yang terjadi di semua untuk beberapa$f_i \in \mathcal O(f_{i+1})$$\mathcal O(f_i) \subseteq \mathcal O(f_{i+1})$$f_j \in \lim_{i\rightarrow\infty} \mathcal O(f_i) = \limsup_{i\rightarrow\infty} \mathcal O(f_i) = \liminf_{i\rightarrow\infty} \mathcal O(f_i) = \bigcup_{n \in \mathbb{N}}\bigcap_{k>n}\mathcal O(f_k)$$j$$\mathcal O(f_i), i \ge n_0$$n_0$ (yang mungkin tergantung pada elemen). Karena urutan kelas meningkat secara monoton keduanya ada dan mereka sama. Ini membenarkan penggunaan .$\lim$

Ya, mungkin saja memiliki rantai tak terbatas.

Saya yakin Anda sudah terbiasa dengan beberapa contoh: Anda memiliki rantai tak terbatas di sini: polinomial tingkat pertumbuhan. Bisakah kamu melangkah lebih jauh? Tentu! Eksponensial tumbuh lebih cepat (secara asimptotik) daripada polinomial mana pun. Dan tentu saja Anda dapat melanjutkan:

$$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots$$ $$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots O(e^x)$$ $O(\mathrm{e}^x) \subseteq O(x\,\mathrm{e}^x) \subseteq O(\mathrm{e}^{2x}) \subseteq O(\mathrm{e}^{\mathrm{e}^x}) \subseteq \ldots$

Anda dapat membangun rantai tak terbatas ke arah lain juga. Jika maka (berpegang pada fungsi positif, karena di sini kita membahas asimptotik fungsi kerumitan). Jadi kita punya misalnya:$f = O(g)$$\dfrac{1}{g} = O\left(\dfrac{1}{f}\right)$

$$O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O\left(\dfrac{e^x}{x^2}\right) \subseteq O\left(\dfrac{e^x}{x}\right) \subseteq O(e^x)$$

Bahkan, mengingat rantai fungsi apa pun , Anda dapat membangun fungsi yang tumbuh lebih cepat daripada semuanya. (Saya berasumsi adalah fungsi dari hingga .) Pertama, mulai dengan ide . Itu mungkin tidak berfungsi karena set dapat tidak terikat. Tetapi karena kita hanya tertarik pada pertumbuhan asimptotik, itu sudah cukup untuk memulai dari yang kecil dan tumbuh secara progresif. Ambil maksimum dari sejumlah fungsi yang terbatas . f $f_1, \ldots, f_n$$f_\infty$$f_i$$\mathbb{N}$$\mathbb{R}_+$$f_\infty(x) = \max \{f_n(x) \mid n \in\mathbb{N}\}$$\{f_n(x) \mid n \in\mathbb{N}\}$

$$f_\infty(x) = \max \{f_n(x) \mid 1 \le n \le N \} \qquad \text{if \(N \le x \lt N+1\)}$$ Kemudian untuk apa pun , , karena . Jika Anda ingin fungsi yang tumbuh lebih cepat ( ), ambil .$N$$f_N \in O(f_\infty)$$\forall x \ge N, f_\infty(x) \ge f_N(x)$$f_\infty = o(f_\infty')$$f_\infty'(x) = x \cdot (1 + f_\infty(x))$