Apakah ada algoritma dunia nyata yang sangat unggul di kelas di bawah ini? [Tutup]

Tadi malam saya berdiskusi dengan programmer lain bahwa meskipun sesuatu mungkin O (1), sebuah operasi yang O (n) dapat mengungguli itu jika ada konstanta besar dalam algoritma O (1). Dia tidak setuju, jadi saya membawanya ke sini.

Apakah ada contoh algoritma yang sangat mengungguli mereka yang ada di kelas di bawahnya? Misalnya, O (n) lebih cepat dari O (1) atau O (n ² ) lebih cepat dari O (n).

Secara matematis ini dapat ditunjukkan untuk fungsi dengan batas atas asimptotik, ketika Anda mengabaikan faktor konstan, tetapi apakah algoritma seperti itu ada di alam liar? Dan di mana saya akan menemukan contohnya? Untuk situasi apa mereka digunakan?

Cari di tabel data yang sangat kecil dan sudah diperbaiki. Tabel hash yang dioptimalkan mungkin O (1) namun lebih lambat dari pencarian biner atau bahkan pencarian linear karena biaya perhitungan hash.

Perkalian matriks. Algoritma naif O (n ^ 3) sering digunakan dalam praktiknya lebih cepat dari pada Strassen O (n ^ 2.8) untuk matriks kecil-ish; dan Strassen's digunakan alih-alih algoritma Coppersmith-Winograd O (n ^ 2.3) untuk matriks yang lebih besar.

Contoh sederhana adalah perbedaan antara berbagai algoritma pengurutan. Mergesort, Heapsort, dan beberapa lainnya adalah O (n log n) . Quicksort adalah kasus terburuk O (n ^ 2) . Tetapi seringkali Quicksort lebih cepat, dan ternyata berkinerja rata-rata seperti O (n log n) . Info lebih lanjut .

Contoh lain adalah pembuatan angka Fibonacci tunggal. Algoritma iteratif adalah O (n) , sedangkan algoritma berbasis matriks adalah O (log n) . Namun, untuk pasangan pertama dari ribuan angka Fibonacci, algoritma berulang mungkin lebih cepat. Ini juga tergantung pada implementasi tentunya!

Algoritma dengan kinerja asimptotik yang lebih baik mungkin mengandung operasi yang mahal yang tidak perlu dengan algoritma dengan kinerja yang lebih buruk tetapi operasi yang lebih sederhana. Pada akhirnya, notasi- O hanya memberi tahu kita sesuatu tentang kinerja ketika argumen yang dioperasikan meningkat secara dramatis (mendekati tak terhingga).

Catatan: Silakan baca komentar oleh @ back2do di bawah ini dan guru-guru lain, karena sebenarnya lebih bermanfaat daripada apa yang saya tulis - Terima kasih untuk semua kontributor.

Saya pikir dari tabel di bawah ini (diambil dari: notasi Big O , cari "Sifat Pesimis Algoritma:"), Anda dapat melihat bahwa O (log n) tidak selalu lebih baik daripada mengatakan, O (n). Jadi, saya kira argumen Anda valid.

Untuk nilai praktisnya n, ya. Ini banyak muncul dalam teori CS. Seringkali ada algoritma yang rumit yang secara teknis memiliki kinerja big-Oh yang lebih baik, tetapi faktor konstannya sangat besar sehingga tidak praktis.

Saya pernah meminta profesor geometri komputasional saya mendeskripsikan sebuah algoritma untuk melakukan triangulasi sebuah poligon dalam waktu linear, tetapi ia selesai dengan "sangat rumit. Saya tidak berpikir ada orang yang benar-benar mengimplementasikannya" (!!).

Selain itu, tumpukan fibonacci memiliki karakteristik yang lebih baik daripada tumpukan normal, tetapi tidak terlalu populer karena mereka tidak berkinerja baik dalam praktik seperti tumpukan biasa. Ini dapat mengalir ke algoritme lain yang menggunakan tumpukan - misalnya, jalur terpendek Dijkstra secara matematis lebih cepat dengan tumpukan fibonacci, tetapi biasanya tidak dalam praktik.

Bandingkan memasukkan ke dalam daftar tertaut dan memasukkan ke dalam array yang bisa diubah ukurannya.

Jumlah data harus cukup besar agar daftar tertaut O (1) menjadi berharga.

Daftar tertaut memiliki overhead tambahan untuk petunjuk dan referensi tambahan berikutnya. Array resizable harus menyalin data sekitar. Penyalinan itu O (n), tetapi dalam praktiknya sangat cepat.

Notasi Big-Oh digunakan untuk menggambarkan laju pertumbuhan suatu fungsi, sehingga ada kemungkinan bahwa algoritma O (1) akan lebih cepat, tetapi hanya sampai pada titik tertentu (faktor konstan).

Notasi umum:

O (1) - Jumlah iterasi (kadang-kadang Anda dapat menyebutnya sebagai waktu pengguna yang dihabiskan oleh fungsi) tidak tergantung pada ukuran input, dan pada kenyataannya konstan.

O (n) - Jumlah iterasi tumbuh dalam proporsi linier dengan ukuran input. Berarti - jika algoritme itu berulang melalui input N, 2 * N kali, itu masih dianggap O (n).

O (n ^ 2) (kuadrat) - Jumlah iterasi adalah ukuran input kuadrat.

Perpustakaan Regex biasanya diimplementasikan untuk melakukan backtracking yang memiliki waktu terburuk kasus eksponensial daripada generasi DFA yang memiliki kompleksitas O(nm).

Backtracking naif dapat menjadi pemain yang lebih baik ketika inputnya tetap berada di jalur cepat atau gagal tanpa perlu mundur secara berlebihan.

(Meskipun keputusan ini tidak hanya berdasarkan kinerja, itu juga untuk memungkinkan referensi kembali.)

Sebuah O(1)algoritma:

def constant_time_algorithm
  one_million = 1000 * 1000
  sleep(one_million) # seconds
end

Sebuah O(n)algoritma:

def linear_time_algorithm(n)
  sleep(n) # seconds
end

Jelas, untuk nilai di nmana pun n < one_million, O(n)algoritma yang diberikan dalam contoh akan lebih cepat daripada O(1)algoritma.

Meskipun contoh ini agak jenaka, semangat ini setara dengan contoh berikut:

def constant_time_algorithm
  do_a_truckload_of_work_that_takes_forever_and_a_day
end

def linear_time_algorithm(n)
  i = 0
  while i < n
    i += 1
    do_a_minute_amount_of_work_that_takes_nanoseconds
  end
end

Anda harus mengetahui konstanta dan koefisien dalam Oekspresi Anda , dan Anda harus mengetahui kisaran yang diharapkan n, untuk menentukan apriori algoritma mana yang akan berakhir lebih cepat.

Jika tidak, Anda harus membandingkan kedua algoritma dengan nilai ndalam kisaran yang diharapkan untuk menentukan posteriori yang akhirnya menjadi lebih cepat.

Penyortiran:

Sortasi penyisipan adalah O (n ^ 2) tetapi mengungguli algoritma penyortiran lainnya O (n * log (n)) untuk sejumlah kecil elemen.

Ini adalah alasan mengapa sebagian besar implementasi semacam menggunakan kombinasi dari dua algoritma. Misalnya, gunakan pengurutan gabungan untuk memecah array besar sampai mereka mencapai ukuran array tertentu, kemudian gunakan pengurutan penyortiran untuk mengurutkan unit yang lebih kecil dan menggabungkan mereka lagi dengan pengurutan gabungan.

Lihat Timsort implementasi default saat ini penyortiran Python dan Java 7 yang menggunakan teknik ini.

The unifikasi algoritma yang digunakan dalam praktek adalah eksponensial dalam kasus terburuk, untuk beberapa masukan patologis.

Ada algoritma penyatuan polinomial , tetapi dalam praktiknya terlalu lambat.

Bubblesort dalam memori dapat mengungguli quicksort ketika program sedang ditukar ke disk atau perlu membaca setiap item dari disk saat membandingkan.

Ini harus menjadi contoh yang bisa dia hubungkan.

Seringkali algoritma yang lebih maju mengasumsikan sejumlah pengaturan (mahal). Jika Anda hanya perlu menjalankannya sekali, Anda mungkin lebih baik dengan metode brute-force.

Sebagai contoh: pencarian biner dan pencarian tabel hash keduanya jauh lebih cepat per pencarian daripada pencarian linear, tetapi mereka meminta Anda untuk mengurutkan daftar atau membangun tabel hash, masing-masing.

Pengurutan akan dikenakan biaya N log (N) dan tabel hash akan dikenakan biaya setidaknya N. Sekarang jika Anda akan melakukan ratusan atau ribuan pencarian, itu masih merupakan tabungan yang diamortisasi. Tetapi jika Anda hanya perlu melakukan satu atau dua pencarian, mungkin hanya masuk akal untuk melakukan pencarian linear dan menghemat biaya startup.

Dekripsi seringkali 0 (1). Misalnya ruang utama untuk DES adalah 2 ^ 56, jadi dekripsi pesan apa pun adalah operasi waktu yang konstan. Hanya saja Anda memiliki faktor 2 ^ 56 di sana sehingga konstanta yang sangat besar.

Implementasi set yang berbeda muncul di benak saya. Salah satu yang paling naif adalah mengimplementasikannya lebih vektor, yang berarti removeserta containsdan karena itu juga addsemua take O (N).
Alternatifnya adalah mengimplementasikannya pada beberapa hash tujuan umum, yang memetakan hash input ke nilai input. Implementasi set seperti itu dilakukan dengan O (1) untuk add, containsdan remove.

Jika kita menganggap N sekitar 10 atau lebih, maka implementasi pertama mungkin lebih cepat. Yang harus dilakukan untuk menemukan elemen adalah membandingkan 10 nilai dengan satu.
Implementasi lain harus memulai segala macam transformasi pintar, yang bisa jauh lebih mahal, daripada membuat 10 perbandingan. Dengan semua overhead, Anda bahkan mungkin memiliki cache miss dan kemudian tidak masalah seberapa cepat solusi Anda secara teori.

Ini tidak berarti, bahwa implementasi terburuk yang dapat Anda pikirkan akan mengungguli yang layak, jika N cukup kecil. Ini hanya berarti untuk N yang cukup kecil, bahwa implementasi yang naif, dengan tapak rendah dan overhead sebenarnya dapat membutuhkan lebih sedikit instruksi dan menyebabkan lebih sedikit cache yang hilang daripada implementasi yang mengutamakan skala, dan karenanya akan lebih cepat.

Anda tidak dapat benar-benar tahu seberapa cepat sesuatu dalam skenario dunia nyata, sampai Anda memasukkannya ke dalam satu dan hanya mengukurnya. Seringkali hasilnya mengejutkan (setidaknya bagi saya).

Ya, untuk N. kecil yang sesuai Akan selalu ada N, di atasnya Anda akan selalu memiliki urutan O (1) <O (lg N) <O (N) <O (N log N) <O (N ^ c ) <O (c ^ N) (di mana O (1) <O (lg N) berarti bahwa pada O (1) algoritma akan mengambil lebih sedikit operasi ketika N cukup besar dan c adalah konstanta tetap yang lebih besar dari 1 ).

Katakanlah algoritma O (1) tertentu membutuhkan operasi f (N) = 10 ^ 100 (a googol) dan sebuah algoritma O (N) membutuhkan operasi g (N) = 2 N + 5. Algoritma O (N) akan memberikan kinerja yang lebih besar sampai Anda N kira-kira googol (sebenarnya ketika N> (10 ^ 100 - 5) / 2), jadi jika Anda hanya berharap N berada di kisaran 1000 hingga satu miliar Anda akan menderita penalti besar menggunakan algoritma O (1).

Atau untuk perbandingan yang realistis, misalkan Anda mengalikan angka n-digit bersama-sama. The Karatsuba algoritma yang paling banyak 3 n ^ (lg 3) operasi (yang kira-kira O (n ^ 1,585)) sedangkan algoritma Schönhage-Strassen adalah O (N log N log log N) yang merupakan urutan lebih cepat , tetapi untuk kutipan wikipedia:

Dalam praktiknya, algoritma Schönhage-Strassen mulai mengungguli metode yang lebih tua seperti Karatsuba dan perkalian Toom-Cook untuk angka di luar 2 ^ 2 ^ 15 hingga 2 ^ 2 ^ 17 (10.000 hingga 40.000 angka desimal). [4] [5] [6 ]

Jadi, jika Anda mengalikan 500 angka angka bersama, tidak masuk akal untuk menggunakan algoritma yang "lebih cepat" oleh argumen O besar.

EDIT: Anda dapat menemukan menentukan f (N) dibandingkan g (N), dengan mengambil batas N-> tak terhingga dari f (N) / g (N). Jika batasnya adalah 0 maka f (N) <g (N), jika batasnya tidak terbatas maka f (N)> g (N), dan jika batasnya adalah konstanta lain maka f (N) ~ g (N) dalam hal notasi O besar.

Metode simpleks untuk pemrograman linier dapat bersifat eksponensial dalam kasus terburuk, sementara algoritma titik interior yang relatif baru dapat bersifat polinomial.

Namun, dalam praktiknya, kasus terburuk eksponensial untuk metode simpleks tidak muncul - metode simpleks cepat dan andal, sementara algoritma titik interior awal terlalu lambat untuk bersaing. (Ada algoritma titik interior sekarang lebih modern yang berada kompetitif - tapi metode simpleks adalah, terlalu ...)

Algoritma Ukkonen untuk membangun percobaan sufiks adalah O (n log n). Ini memiliki keuntungan menjadi "online" - yaitu, Anda dapat menambahkan teks secara bertahap.

Baru-baru ini, algoritma lain yang lebih kompleks diklaim lebih cepat dalam praktiknya, sebagian besar karena akses memori mereka memiliki lokalitas yang lebih tinggi, sehingga meningkatkan pemanfaatan cache prosesor dan menghindari warung pipa CPU. Lihat, misalnya, survei ini , yang mengklaim bahwa 70-80% waktu pemrosesan dihabiskan untuk menunggu memori, dan makalah ini menjelaskan algoritma "wotd".

Upaya sufiks penting dalam genetika (untuk mencocokkan urutan gen) dan, yang agak kurang penting, dalam penerapan kamus Scrabble.

Selalu ada algoritma tercepat dan terpendek untuk masalah yang terdefinisi dengan baik . Ini hanya murni secara teoritis algoritma tercepat (asimptotik).

Diberi deskripsi masalah P dan sebuah contoh untuk itu masalah saya , itu menyebutkan semua algoritma mungkin A dan bukti Pr , memeriksa setiap pasangan seperti apakah Pr merupakan bukti valid yang A adalah algoritma asimtotik tercepat untuk P . Jika menemukan bukti seperti itu, kemudian mengeksekusi A di saya .

Mencari pasangan masalah-bukti ini memiliki kompleksitas O (1) (untuk masalah tetap P ), jadi Anda selalu menggunakan algoritma tercepat asimptotik untuk masalah tersebut. Namun, karena konstanta ini sangat luar biasa dalam hampir semua kasus, metode ini sama sekali tidak berguna dalam praktiknya.

Banyak bahasa / kerangka kerja menggunakan pencocokan pola naif untuk mencocokkan string, bukan KMP . Kami mencari string seperti Tom, New York daripada ababaabababababaababababababab.