Apa arti algoritma yang lebih cepat dalam ilmu komputer teoretis?

Jika ada algoritma yang berjalan dalam waktu untuk beberapa masalah A, dan seseorang muncul dengan algoritma yang berjalan dalam waktu, , di mana , apakah ini dianggap perbaikan dari algoritma sebelumnya?O ( f ( n ) / g ( n ) ) g ( n ) = o ( f ( n ) $O(f(n))$$O(f(n)/g(n))$$g(n) = o(f(n))$

Apakah masuk akal, dalam konteks ilmu komputer teoretis, untuk menghasilkan algoritma seperti itu?

Tidak, suatu algoritma yang berjalan dalam waktu $O(f(n)/g(n))$ , di mana $g(n) = o(f(n))$ , tidak selalu dianggap sebagai peningkatan. Sebagai contoh, anggaplah bahwa $f(n) = n$ dan $g(n) = 1/n$ . Kemudian $O(f(n)/g(n)) = O(n^2)$ adalah batas waktu yang lebih buruk daripada$O(f(n)) = O(n)$ .

Untuk meningkatkan algoritme yang berjalan dalam waktu $f(n)$ , Anda perlu membuat algoritma yang berjalan dalam waktu $o(f(n))$ , yaitu, dalam waktu $g(n)$ untuk beberapa fungsi $g(n) = o(f(n))$ .

Jika yang Anda tahu adalah bahwa suatu algoritma berjalan dalam waktu , maka tidak jelas apakah suatu algoritma yang berjalan dalam waktu O ( g ( n ) ) adalah peningkatan, apa pun f ( n ) , g ( n ) adalah. Ini karena O besar hanya batas atas pada waktu berjalan. Sebaliknya, itu adalah umum untuk mempertimbangkan kasus terburuk waktu kompleksitas, dan untuk memperkirakan sebagai besar Θ bukan hanya sebagai besar O .$O(f(n))$$O(g(n))$$f(n),g(n)$$\Theta$$O$

Ingat bahwa Notasi dimaksudkan untuk menganalisis bagaimana tugas tumbuh untuk ukuran yang berbeda dari input, dan secara khusus daun keluar faktor perkalian, jangka menurunkan-order, dan konstanta.$O(...)$

Misalkan Anda memiliki algoritma yang runtime aktualnya adalah 1 n 2 + 2 n + 1 (dengan asumsi Anda benar-benar dapat menghitung instruksi dan mengetahui waktu yang tepat dan seterusnya, yang diakui sebagai asumsi besar dalam sistem modern). Lalu anggaplah Anda datang dengan algoritma baru yang kebetulan menjadi O ( n ) , tetapi runtime yang sebenarnya adalah 1000 n + 5000 . Andaikan Anda tahu perangkat lunak untuk menggunakan algoritma ini tidak akan pernah melihat ukuran masalah n > 10 .$O(n^2)$$1n^2+2n+1$$O(n)$$1000n + 5000$$n>10$

Jadi, mana yang akan Anda pilih - algoritma yang akan memakan waktu 15.000 unit, atau O ( n 2 ) yang hanya akan mengambil 121 unit? Sekarang jika perangkat lunak Anda berevolusi untuk menangani ukuran masalah n > 100000 , yang mana yang akan Anda pilih? Apa yang akan Anda lakukan jika ukuran masalah Anda sangat bervariasi?$O(n)$$O(n^2)$$n>100000$

Secara umum, apa artinya itu adalah, untuk ukuran input apa pun yang cukup besar, waktu berjalan terburuk dari algoritma lama lebih lambat daripada yang baru. Itu setara dengan formalisme , di mana g adalah kompleksitas waktu dari algoritma baru dan f kompleksitas waktu yang lama.$g(n) \in o\bigl(f\left(n\right)\bigr)$$g$$f$

Namun, kadang-kadang, para ilmuwan komputer peduli dengan kinerja rata-rata. Contoh klasiknya adalah Quicksort: runtime kasus terburuknya adalah sedangkan kita mengenal orang lain yang berjalan dalam waktu Θ ( n log n ) , tetapi dalam praktiknya banyak digunakan karena waktu berjalan rata-rata yang baik. Selain itu dapat diubah untuk berjalan sangat cepat dalam kasus-kasus yang paling sering terjadi di alam liar, seperti array yang sebagian besar dalam urutan yang benar.$\Theta(n^2)$$\Theta(n \log n)$

Dan kadang-kadang, bahkan para ilmuwan komputer teoretis menggunakan "lebih cepat" seperti orang normal. Sebagai contoh, sebagian besar implementasi kelas String memiliki Optimasi String Pendek (juga disebut Optimasi String Kecil), meskipun hanya mempercepat untuk string pendek dan overhead murni untuk yang lebih lama. Ketika ukuran input semakin besar dan semakin besar, waktu operasi String yang dijalankan dengan SSO akan semakin tinggi dengan istilah konstanta yang kecil, jadi menurut definisi yang saya berikan di paragraf pertama, menghapus SSO dari kelas String membuatnya lebih cepat . ”Namun dalam praktiknya, sebagian besar string berukuran kecil, sehingga SSO membuat sebagian besar program yang menggunakannya lebih cepat, dan sebagian besar profesor ilmu komputer tahu lebih baik daripada berkeliling menuntut bahwa orang hanya berbicara tentang pesanan kompleksitas waktu asimptotik .

Tidak ada satu definisi terpadu tentang apa "algoritma yang lebih cepat" itu. Tidak ada badan pengatur yang memutuskan apakah suatu algoritma lebih cepat dari yang lain.

Untuk menunjukkan mengapa ini terjadi, saya ingin menawarkan dua skenario berbeda yang menunjukkan konsep keruh ini.

Contoh pertama adalah algoritme yang mencari daftar data unordered yang tertaut. Jika saya dapat melakukan operasi yang sama dengan sebuah array, saya tidak memiliki perubahan pada ukuran kinerja Oh yang besar. Kedua pencarian adalah O (n). Jika saya hanya melihat nilai-nilai Oh yang besar, saya bisa mengatakan bahwa saya tidak membuat perbaikan sama sekali. Namun, diketahui bahwa pencarian array lebih cepat daripada berjalan dalam daftar tertaut di sebagian besar kasus, jadi orang dapat memutuskan bahwa itu membuat algoritma "lebih cepat," meskipun Oh besar tidak berubah.

Jika saya dapat menggunakan contoh tradisional pemrograman robot untuk membuat sandwich PBJ, saya bisa menunjukkan apa yang saya maksud dengan cara lain. Pertimbangkan saja titik di mana seseorang membuka toples selai kacang.

Pick up the jar
Grab the lid
Unscrew the lid

Melawan

Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Put the jar back down
Pick up the jar
Grab the lid
Unscrew the lid

Bahkan dalam pengaturan teoretis paling akademis yang dapat saya pikirkan, Anda akan menemukan bahwa orang menerima bahwa algoritma pertama lebih cepat daripada yang kedua, meskipun hasil notasi Oh besar adalah sama.

Sebaliknya, kita dapat mempertimbangkan algoritma untuk memecah enkripsi RSA. Saat ini, dianggap bahwa proses ini mungkin O (2 ^ n), di mana n adalah jumlah bit. Pertimbangkan algoritma baru yang menjalankan n ^ 100 lebih cepat Ini berarti proses baru saya berjalan di O (2 ^ n / n ^ 100). Namun, dalam dunia kriptografi, percepatan polinomial ke algoritma eksponensial secara tradisional tidak dianggap sebagai kecepatan teoretis sama sekali. Ketika melakukan bukti keamanan, diasumsikan bahwa penyerang dapat menemukan salah satu dari percepatan ini, dan itu tidak akan berpengaruh.

Jadi dalam satu keadaan, kita dapat mengubah O (n) menjadi O (n), dan menyebutnya lebih cepat. Dalam keadaan yang berbeda, kita dapat mengubah O (2 ^ n) menjadi O (2 ^ n / n ^ 100), dan mengklaim tidak ada kecepatan yang berarti sama sekali. Inilah sebabnya saya katakan tidak ada satu definisi yang disatukan untuk "algoritma yang lebih cepat." Itu selalu tergantung secara kontekstual.

$A(n) \in O(f(n))$

$$\exists \ 0 \le c_f \lt \infty \mid \ \limsup_{n \to \infty} \frac{A(n)}{f(n)} = c_f$$

$g(n)$$\limsup_{n\to\infty} g(n) = \infty$$h(n) = \frac{f(n)}{g(n)}$

$A'(n)$$O(h(n))$$A(n)$$O(h(n))$

$$\exists \ 0 \le c_h \lt \infty \mid \ \limsup_{n \to \infty} \frac{A(n)}{h(n)} = c_h$$

Dengan menggunakan aturan batas, kita juga dapat menulis:

$$c_h = \limsup_{n \to \infty} \frac{A(n)}{h(n)} = \limsup_{n \to \infty} \frac{A(n)g(n)}{f(n)} = c_f \cdot \limsup_{n \to \infty} g(n)$$

$c_h \lt \infty$$c_f = 0$

$c_f \neq 0$$A(n) \notin O(h(n))$

$A'(n)$$A(n)$$A(n) \in \Theta(f(n))$$g(n)$

$A(n) \in O(f(n))$$A'(n)$$A(n)$$O(h(n))$