Apa itu Algoritma Efisien?

Dari sudut pandang perilaku asimptotik, apa yang dianggap sebagai algoritma "efisien"? Apa standar / alasan untuk menggambar garis pada titik itu? Secara pribadi, saya akan berpikir bahwa apa pun yang mungkin secara naif saya sebut "sub-polinomial", sehingga seperti akan efisien dan apa pun yang akan "tidak efisien". Namun, saya pernah mendengar apa pun yang urutan polinomialnya disebut efisien. Apa alasannya?n 1 + ϵ Ω ( n 2$f(n) = o(n^2)$$n^{1+\epsilon}$$\Omega(n^2)$

Itu tergantung pada konteksnya. Dalam ilmu komputer teoretis, biasanya setiap algoritma waktu polinomial dianggap 'efisien'. Dalam algoritma perkiraan misalnya runtime akan dianggap efisien, meskipun dalam praktiknya tidak akan dapat digunakan untuk nilai wajar apa pun dari . Algoritma untuk SAT yang berjalan di akan menjadi terobosan yang luar biasa. ϵ n 2 $n^{1/\epsilon^{1/\epsilon}}$$\epsilon$$n^{2^{100}}$

Dalam algoritme klasik, yaitu algoritme dari tahun 80-an dan sebelumnya, runtime di bawah atau lebih (pikirkan penggandaan matriks, pencocokan biaya minimum, aliran, pemrograman linier) dianggap efisien. Mereka masih dianggap efisien oleh kebanyakan orang, menurut saya. Tentu saja algoritma tidak dianggap efisien jika algoritma diketahui, seperti untuk menyortir misalnya.n 2 n log $n^3$$n^2$$n\log n$

Saat ini ada kecenderungan ke arah algoritma sublinear atau streaming algoritma yang mampu menangani data terabyte. Coba gunakan perkalian matriks untuk menghitung peringkat halaman semua halaman dalam indeks Google. Itu tidak akan berhasil.

Tentu saja, walaupun tentu saja bermanfaat, runtime asimtotik dari suatu algoritma tidak menceritakan keseluruhan cerita. Ada beberapa algoritma yang memiliki runtime asimptotik yang baik, tetapi konstanta yang sangat besar sehingga tidak dapat digunakan secara efektif. Pernah. Lipton menyebut mereka Algoritma Galactic . Robert Sedgewick bahkan menyatakan bahwa batas kasus terburuk "sering tidak berguna untuk prediksi, sering tidak berguna untuk jaminan" dan "analisis kasus terburuk tidak berguna untuk memprediksi kinerja" dalam pidatonya Puting the Science Back Into Computer Science .

2 sen saya dari sudut algoritma terdistribusi: Ketika melihat jaringan skala besar (P2P, jejaring sosial, dll.) Algoritma terdistribusi dianggap efisien jika waktu operasinya adalah untuk beberapa konstan dan algoritma menggunakan pesan bit . Perhatikan bahwa persyaratan ukuran pesan biasanya diberikan lebih penting daripada waktu berjalan, khususnya untuk masalah "global" yang memiliki batas bawah yang lebih besar pada waktu berjalan, misalnya MST yang didistribusikan.c > 0 O ( log n $O(\log^c n)$$c>0$ $O(\log n)$

Alasan di baliknya adalah bahwa, dari perspektif perilaku asimptotik, laju pertumbuhan polinom secara sepele lebih kecil daripada laju pertumbuhan super-polinomial. Dalam prakteknya, algoritma waktu polinomial berjalan lebih cepat daripada algoritma waktu super-polinomial ketika ukuran input bertambah.

Tentu saja, tidak ada yang akan mengatakan bahwa algoritma dengan kompleksitas polinomial, misalnya, adalah "efisien", tetapi mayoritas algoritma jarang melebihi kompleksitas .O ( n 5$O(n^{2000})$$O(n^5)$

Pertimbangan praktis bahkan dapat mengarahkan Anda untuk mengatakan bahwa tidak efisien untuk memproses input yang sangat besar, dan inilah mengapa kami mencoba untuk membuktikan batas bawah dan untuk merancang algoritma berurutan yang cocok dengan batas bawah ini pada satu sisi, dan menggunakan algoritma paralel di sisi lain. Untuk beberapa masalah, jika Anda bersedia menerima jaminan probabilistik, Anda bahkan dapat memanfaatkan algoritma waktu sub-linear (sangat cepat, tetapi mungkin gagal memberikan jawaban yang benar dengan probabilitas yang sangat kecil). $O(n^2)$

Secara teori, suatu algoritma dikatakan efisien jika waktu terburuknya dibatasi oleh polinomial dalam panjang inputnya. Alasannya karena polinomial memiliki sifat penutupan yang bagus. Menambahkan, mengalikan, menyusun polinomial adalah operasi yang menghasilkan polinomial dan ini bagus jika Anda mengurangi masalah satu sama lain.

Tentu saja kesenjangan antara polinomial dan eksponensial menjadi sangat besar karena panjang input meningkat sehingga algoritma waktu polinomial jauh lebih baik. Dalam prakteknya, algoritma waktu polinomial mungkin membutuhkan waktu lama sebelum pemutusan tetapi mungkin itu adalah algoritma yang optimal (yang terbaik) dalam hal ini saya akan mengatakan itu efisien.

Beberapa masalah mudah, beberapa sulit. Apakah suatu algoritma "efisien" tergantung pada seberapa baik itu dibandingkan dengan kompleksitas masalah yang melekat. Jika Anda menemukan algoritme yang memperhitungkan faktor n angka dalam operasi O ( ), dan saya menemukan algoritma yang mengurutkan n angka dalam operasi O ( ), maka algoritme Anda lebih efisien (karena mengalahkan apa pun yang diketahui untuk umat manusia oleh faktor yang sangat besar, sementara milikku selambat yang Anda harapkan dari seorang pemula absolut).n $n^3$$n^2$