Apa artinya dengan mengatakan "Asymptotically lebih efisien"?

Apa artinya ketika kita mengatakan bahwa suatu algoritma secara asimptot lebih efisien daripada ?$X$$Y$

• $X$ akan menjadi pilihan yang lebih baik untuk semua input.
• $X$ akan menjadi pilihan yang lebih baik untuk semua input kecuali input kecil.
• $X$ akan menjadi pilihan yang lebih baik untuk semua input kecuali input besar.
• $Y$ akan menjadi pilihan yang lebih baik untuk input kecil.

Tautan untuk pertanyaan ini ada di sini.

http://quiz.geeksforgeeks.org/algorithms-analysis-of-algorithms-question-16/

Saya pikir suatu algoritma yang lebih efisien asimptotik seharusnya bekerja untuk semua input, tetapi saya tidak mendapatkan alasan di balik "Ini bekerja untuk semua input kecuali yang kecil".

Pertama, kedua algoritma "bekerja" untuk semua input. Pertanyaannya adalah tentang kinerja.

Jawaban atas pertanyaan itu agak jelek. Salah satu cara untuk mengatakan satu algoritma secara asimptot lebih efisien daripada yang lain adalah jika ada beberapa ukuran input (khusus masalah) sehingga untuk setiap ukuran input yang lebih besar algoritma yang lebih efisien akan mengambil lebih sedikit "langkah komputasi", biasanya dengan beberapa ukuran abstrak, misalnya jumlah perbandingan.

Gagasan dari jawaban adalah bahwa suatu algoritma asimptotik yang lebih efisien mungkin masih memerlukan lebih banyak langkah sebelum ukuran input itu. Ini dapat menjadi kasus bahwa algoritma asimtotik yang lebih efisien membutuhkan langkah-langkah lebih sedikit untuk semua input, tetapi tidak harus menjadi kasus dan dalam praktiknya biasanya tidak. Jadi kata yang lebih baik dari jawaban "benar" adalah " akan menjadi pilihan yang lebih baik untuk semua input kecuali mungkin input kecil".$X$

Kata-katanya masih tidak terlalu bagus. Pertama, banyak faktor yang menentukan algoritma apa yang merupakan "pilihan yang lebih baik", tetapi saya akan memberi mereka bahwa maksudnya cukup jelas dalam kasus ini. Masalah sebenarnya adalah "kecil" dan "besar". Salah satu makalah favorit saya adalah Algoritma Tercepat dan Terpendek untuk Semua Masalah yang Didefinisikan dengan Baik . Makalah ini menjelaskan suatu algoritma yang diberikan setiap spesifikasi fungsi dan bukti bahwa hal itu dapat dihitung dalam waktu polinomial akan menghitung bahwa fungsi di optimal kompleksitas waktu dalam faktor ditambah istilah aditif. Sebagai contoh,$5$ , itu akan menghasilkan algoritma pengurutan yang O ( n lg n ) . Bahkan, itu akan menghasilkan algoritma yang 5 c n lg n + o ( n lg n ) di mana c adalah faktor konstan darialgoritma optimalasimptotik^*. Ini luar biasa. Hanya ada satu masalah:istilah konstan - tersembunyi di o ( n lg n $O(n^2)$$O(n\lg n)$$5cn\lg n + o(n\lg n)$$c$$o(n\lg n)$dalam contoh ini - merender algoritma hampir pasti sangat tidak mungkin untuk hampir semua masalah nyata. Apa yang saya maksud dengan "sama sekali tidak layak"? Maksudku kematian panas alam semesta akan terjadi berkali-kali sebelum algoritma itu selesai. Namun demikian, untuk input "besar" yang sesuai, itu akan lebih cepat daripada semacam gelembung. Maksud saya adalah hampir pasti secara fisik tidak mungkin untuk menuliskan dengan cara apa pun input yang "sesuai besar", apalagi menghitungnya.

$X$$Y$

$c$$c$

Apa yang biasanya orang maksud ketika mereka mengatakan sesuatu seperti ini adalah:

$T_A$$T_B$$A$$B$$T_A \in o(T_B)$

$X$

Secara khusus, tidak ada pernyataan yang Anda usulkan mengikuti, meskipun orang sering menyarankan yang kedua lakukan.

Sayangnya, komunitas yang lebih luas dari orang-orang yang berurusan dengan algoritma merangkul terminologi yang berbatasan dengan hampa demi kesederhanaan. (Membuat pernyataan yang tepat dan bermanfaat tentang algoritma sulit!)

Anda mungkin tertarik dengan pertanyaan referensi kami .

Algoritma X dikatakan secara asimptotik lebih baik daripada Y jika X membutuhkan waktu lebih kecil dari y untuk semua ukuran input n lebih besar dari nilai n0 di mana n0> 0.

$T_A(n) = n+1$$T_B(n) = n$

Saya sarankan Anda belajar ilmu komputer dari sumber daya CS, bukan dari programmer yang pernah membaca tentang hal-hal di Wikipedia sekali. (Ya, itu keras, tetapi saya telah melihat terlalu banyak kepalsuan yang disebarkan di kalangan programmer, bahkan pada SO.)

"Asymptotically lebih efisien" berarti "lebih efisien untuk semua masalah di atas ukuran tertentu". Ia tidak mengatakan apa "ukuran tertentu" itu, dan tidak mengatakan apa yang terjadi sebelum "ukuran tertentu" itu.

Jadi semua jawaban kecuali yang kedua jelas salah, karena "Asymptotically lebih efisien" tidak mengatakan apa-apa tentang ukuran input yang kecil sama sekali. Tapi yang kedua juga bermasalah.

$10^{30}$$10^{30}$$10^{40}$

$10^{15}$