Contoh algoritma di mana istilah orde rendah mendominasi runtime untuk input praktis?

Notasi O-besar menyembunyikan faktor konstan, sehingga beberapa algoritma ada yang tidak layak untuk ukuran input yang masuk akal karena koefisien pada term begitu besar.$O(n)$$n$

Apakah ada algoritma yang dikenal yang runtime-nya adalah tetapi dengan beberapa istilah orde-rendah yang begitu besar sehingga untuk ukuran input yang masuk akal ia sepenuhnya mendominasi runtime? Saya ingin menggunakan algoritme seperti ini sebagai contoh dalam kursus algoritme, karena memberikan alasan yang bagus mengapa notasi O besar tidak pernah terjadi.$O(f(n))$$o(f(n))$

Terima kasih!

Kriptografi adalah contohnya, jika bersifat merosot. Misalnya, melanggar enkripsi AES adalah - yang harus Anda lakukan adalah menemukan kunci yang tepat di antara angka yang terbatas, atau atau tergantung pada ukuran kunci ( berasumsi bahwa cukup teks plainteks diketahui menentukan kunci secara jelas). Namun bahkan operasi akan mengambil semua komputer hari ini (satu miliar atau sekitar itu, masing-masing melakukan sekitar satu miliar operasi per sceond) lebih dari umur alam semesta (sekitar satu miliar miliar detik).$O(1)$$2^{128}$$2^{192}$$2^{256}$$2^{128}$

Cara yang sedikit berbeda untuk mengilustrasikan mengapa big-O bukanlah segalanya adalah dengan mengatakan bahwa kita kadang-kadang menggunakan algoritma yang berbeda untuk ukuran input yang kecil. Misalnya, ambil quicksort. Dengan pivot pilihan yang tepat (yang merupakan bisnis rumit!), Itu . Quicksort beroperasi dengan membagi-dan-menaklukkan: setiap contoh melibatkan banyak penyortiran array kecil. Untuk array kecil, metode kuadratik seperti jenis sisipan berkinerja lebih baik. Jadi untuk kinerja terbaik, quicksort dari array besar melibatkan banyak jenis penyisipan berjalan untuk ukuran kecil.$O(n \lg n)$

Dua contoh muncul dari bidang kompleksitas parameter dan algoritma FPT. Ini mungkin tidak persis apa yang Anda cari, tapi begini saja.

Pertimbangkan masalah grafik, seperti 3-COLORING atau HAM-CYCLE. Kedua masalah dapat diekspresikan dalam logika urutan kedua monadik, dan karenanya dapat diputuskan dalam waktu linier grafik dengan treewidth terikat. Ini adalah hasil dari Bruno Courcelle , tetapi algoritma yang dihasilkan jauh dari praktis.

$O(p^{9p/2})L$$O(p^{2p}L)$$p$$L$

agak terkait dengan pertanyaan Anda adalah algoritma yang diketahui memiliki kinerja yang baik secara teoritis tetapi tidak digunakan pada masalah nyata karena ketidakpraktisan pada contoh yang lebih kecil. dengan kata lain seperti yang Anda minta, "kinerja yang diiklankan" hanya mungkin untuk input besar dalam teori, tidak terlihat dalam aplikasi praktis. ini kadang-kadang tercermin dalam perkiraan Big-Oh, di waktu lain tidak tepat. beberapa algoritma memiliki "kinerja" teoretis yang baik tetapi sangat kompleks secara logis dan belum pernah diterapkan oleh siapa pun, dan oleh karena itu "kinerja" pada ukuran contoh praktis bahkan tidak dikenal, misalnya dengan masalah Maximum Flow .

• pengujian primality di P melalui algoritma AKS

• Algoritma multiplikasi matriks Coppersmith-winograd

• lihat juga apakah algoritma aliran maksimum state-of-the-art praktis? tcs.se

• lihat juga algoritma yang kuat terlalu rumit untuk mengimplementasikan tcs.se

• algoritme galaksi blog RJLipton

Ini semacam lelucon tetapi memiliki sisi serius ...

$O(n\log n)$$O(n^2)$