Fungsi penyortiran berdasarkan pertumbuhan asimptotik

Asumsikan saya memiliki daftar fungsi, misalnya

$\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots$

Bagaimana cara saya mengurutkannya asimptotik, yaitu setelah relasi didefinisikan oleh

$\qquad f \leq_O g \iff f \in O(g)$ ,

dengan asumsi mereka memang sebanding secara berpasangan (lihat juga di sini )? Menggunakan definisi tampaknya canggung, dan seringkali sulit untuk membuktikan keberadaan konstanta yang cocok dan .$O$$c$$n_0$

Ini tentang ukuran kompleksitas, jadi kami tertarik pada perilaku asimptotik sebagai , dan kami menganggap bahwa semua fungsi hanya mengambil nilai non-negatif ( ).$n \to +\infty$$\forall n, f(n) \ge 0$

Jika Anda ingin bukti yang kuat, lemma berikut ini sering kali berguna. lebih berguna daripada definisi.

$c = \lim_{n\to\infty} \frac{f(n)}{g(n)}$

• $c=0 \qquad \ \,\iff f \in o(g)$ ,
• $c \in (0,\infty) \iff f \in \Theta(g)$ dan
• $c=\infty \quad \ \ \ \iff f \in \omega(g)$ .

Dengan ini, Anda harus dapat memesan sebagian besar fungsi yang muncul dalam analisis algoritma¹. Sebagai latihan, buktikan!

Tentu saja Anda harus dapat menghitung batas yang sesuai. Beberapa trik yang berguna untuk memecah fungsi-fungsi rumit menjadi yang mendasar adalah:

• Ekspresikan kedua fungsi sebagai dan bandingkan eksponen; jika rasio mereka cenderung ke atau , demikian juga hasil bagi aslinya. 0 $e^{\dots}$$0$$\infty$

• Lebih umum: jika Anda memiliki cembung, terus terdiferensialkan dan ketat meningkatkan fungsi sehingga Anda dapat menulis ulang quotient Anda sebagai$h$

  $\qquad \displaystyle \frac{f(n)}{g(n)} = \frac{h(f^*(n))}{h(g^*(n))}$ ,

  dengan dan$g^* \in \Omega(1)$

  $\qquad \displaystyle \lim_{n \to \infty} \frac{f^*(n)}{g^*(n)} = \infty$ ,

  kemudian

  $\qquad \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$ .

  ^{Lihat di sini untuk bukti ketat aturan ini (dalam bahasa Jerman).}

• Pertimbangkan kelanjutan fungsi Anda di atas real. Anda sekarang dapat menggunakan aturan L'Hôpital ; perhatikan kondisinya²!

• Lihatlah ekuivalen diskritnya , Stolz-Cesàro .

• Saat faktorial muncul, gunakan rumus Stirling :

  $\qquad \displaystyle n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$

Juga berguna untuk menyimpan kumpulan hubungan dasar yang Anda buktikan sekali dan sering gunakan, seperti:

• logaritma tumbuh lebih lambat dari polinomial, yaitu

  α , β > $\qquad\displaystyle (\log n)^\alpha \in o(n^\beta)$ untuk semua .$\alpha, \beta > 0$

• urutan polinomial:

  α<$\qquad\displaystyle n^\alpha \in o(n^\beta)$ untuk semua .$\alpha < \beta$

• polinomial tumbuh lebih lambat daripada eksponensial:

  αc>$\qquad\displaystyle n^\alpha \in o(c^n)$ untuk semua dan .$\alpha$$c > 1$

---

Dapat terjadi bahwa lemma di atas tidak berlaku karena batas tidak ada (misalnya ketika fungsi berosilasi). Dalam hal ini, pertimbangkan karakterisasi berikut kelas Landau menggunakan limau superior / inferior :

Dengan kami memiliki$c_s := \limsup_{n \to \infty} \frac{f(n)}{g(n)}$

• $0 \leq c_s < \infty \iff f \in O(g)$ dan
• $c_s = 0 \iff f \in o(g)$ .

Dengan kami memiliki$c_i := \liminf_{n \to \infty} \frac{f(n)}{g(n)}$

• $0 < c_i \leq \infty \iff f \in \Omega(g)$ dan
• $c_i = \infty \iff f \in \omega(g)$ .

Selanjutnya,

• $0 < c_i,c_s < \infty \iff f \in \Theta(g) \iff g \in \Theta(f)$ dan
• $c_i = c_s = 1 \iff f \sim g$ .

---

Periksa di sini dan di sini jika Anda bingung dengan notasi saya.

---

¹ Nota bene: Kolega saya menulis fungsi Mathematica yang melakukan ini dengan sukses untuk banyak fungsi, sehingga lemma benar-benar mengurangi tugas menjadi perhitungan mekanis.

² Lihat juga di sini .

Kiat lain: terkadang menerapkan fungsi monoton (seperti log atau exp) ke fungsi yang membuat semuanya lebih jelas.

Skiena menyediakan daftar hubungan dominasi yang tersortir di antara fungsi-fungsi paling umum dalam bukunya, The Algorithm Design Manual:

$$n!\gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon} \gg n \lg n \gg n \gg n^{1/2}$$ $$\gg \lg^2n \gg \lg n \gg \frac{\lg n}{\lg\lg n} \gg \lg\lg n \gg \alpha(n) \gg 1$$

Di sini menunjukkan fungsi Ackermann terbalik .$\alpha(n)$

Kiat: gambar grafik fungsi-fungsi ini menggunakan sesuatu seperti Wolfram Alpha untuk merasakan bagaimana mereka tumbuh. Perhatikan bahwa ini tidak terlalu tepat, tetapi jika Anda mencobanya untuk jumlah yang cukup besar, Anda harus melihat pola pertumbuhan komparatif. Ini tentu saja bukan pengganti bukti.

Misalnya, coba: plot log (log (n)) dari 1 hingga 10.000 untuk melihat grafik individual atau plot log (log (n)) dan plot log (n) dari 1 hingga 10.000 untuk melihat perbandingan.

Saya menyarankan untuk melanjutkan sesuai dengan definisi berbagai notasi. Mulailah dengan beberapa ekspresi sewenang-wenang, dan tentukan urutannya, seperti diuraikan di bawah ini. Kemudian, untuk setiap elemen tambahan, temukan posisinya di daftar yang disortir menggunakan pencarian biner dan bandingkan seperti di bawah ini. Jadi, misalnya, mari kita urutkan dan , dua fungsi pertama n, untuk memulai daftar.$n^{\log\log n}$$2^n$

Kami menggunakan properti yang untuk menulis ulang ekspresi pertama sebagai . Kita kemudian dapat melanjutkan untuk menggunakan definisi untuk menunjukkan bahwa , karena untuk konstanta apa pun , ada sedemikian rupa sehingga untuk , .$n = 2^{\log n}$$n^{\log\log n} = (2^{\log n})^{\log\log n} = 2^{\log n\log\log n}$$n^{\log\log n} = 2^{\log n\log\log n} \in o(2^n)$$c > 0$$n_0$$n \geq n_0$$c(n^{\log\log n}) = c(2^{\log n\log\log n}) < 2^n$

Selanjutnya, kami mencoba . Kami membandingkannya dengan , elemen terbesar yang telah kami tempatkan sejauh ini. Karena , kami juga menunjukkan bahwa .$3^n$$2^n$$3^n = (2^{\log 3})^n = 2^{n\log3}$$2^n \in o(3^n) = o(2^{n \log 3})$

Dll

Berikut daftar dari Wikipedia , Semakin rendah tabel semakin tinggi kelas kompleksitasnya;

$$\begin{array}{|l|l|} \hline Name & \text{Running Time} \\ \hline \text{Constant time} & \mathcal{O}(1) \\ \text{Inverse Ackermann time} & \mathcal{O}(a(n)) \\ \text{Iterated logarithmic time} & \mathcal{O}(\log^*n) \\ \text{Log-logarithmic} & \mathcal{O}(n \log n) \\ \text{Logarithmic time} & \mathcal{O}(\log n) \\ \text{Polylogarithmic time} & poly(\log n) \\ \text{Fractional power} & \mathcal{O}(n^c) ,\text{where } 0<c<1 \\ \text{Linear time} & \mathcal{O}(n) \\ \text{"n log star n" time} & \mathcal{O}(n \log^* n) \\ \text{Quasilinear time} & \mathcal{O}(n \log n) \\ \text{Quadratic time} & \mathcal{O}(n^2) \\ \text{Cubic time} & \mathcal{O}(n^3) \\ \text{Polynomial time} & poly(n) = 2^{\mathcal{O}(\log n)} \\ \text{Quasi-polynomial time} & 2^{\mathcal{O}(poly(\log n))} \\ \text{Sub-exponential time (first definition)} & \mathcal{O}(2^{n^{\epsilon}}), \epsilon >0 \\ \text{Sub-exponential time (second definition)} & 2^{\mathcal{o}(n)}\\ \text{Exponential time(with linear exponent)} & 2^{\mathcal{O}(n)} \\ \text{Exponential time} & 2^{poly(n)} \\ \text{Factorial time} & \mathcal{O}(n!) \\\hline \end{array}$$

catatan:$poly(x) = x^{\mathcal{O}(1)}$