Konstanta Tersembunyi dalam Kompleksitas Algoritma

Untuk banyak masalah, algoritma dengan kompleksitas asimptotik terbaik memiliki faktor konstan yang sangat besar yang disembunyikan oleh notasi O besar. Ini terjadi dalam perkalian matriks, perkalian integer (khususnya, algoritma multiplikasi integer O (n log n) baru-baru ini dari Harvey dan van der Hoeven), jaringan sortasi rendah-kedalaman dan menemukan grafik di bawah umur, untuk membuat beberapa. Algoritma seperti itu kadang-kadang disebut algoritma Galactic.

Perhatikan bahwa untuk algoritma lain, seperti penyortiran umum dan penambahan bilangan bulat, algoritma dikenal dengan kompleksitas asimptotik yang optimal dan faktor kecil yang konstan.

Apa penelitian yang telah dilakukan dalam memisahkan algoritma yang terdahulu dari algoritma yang terakhir, dari perspektif teoretis?

Saya sadar bahwa konstanta tersembunyi sering dihilangkan untuk menyembunyikan perbedaan antara model komputasi yang berbeda. Namun, saya yakin bahwa di bawah berbagai model yang berbeda, algoritma Galactic ini akan lebih lambat daripada algoritma asymptotically buruk untuk input ukuran satu miliar, misalnya. Perbedaannya tidak halus, dalam beberapa kasus. Apakah sudah dibuat ketat?

Sebagai contoh, seseorang dapat menciptakan model perhitungan yang sangat sederhana, seperti mesin von Neumann dengan ISA yang sangat sederhana, dan kemudian mengimplementasikan algoritme dan mengikat waktu menjalankannya dengan konstanta eksplisit. Apakah ini sudah dilakukan untuk berbagai algoritma?

cc.complexity-theory ds.algorithms time-complexity isaacg
sumber

Algoritma perkalian integer cepat bukan galaksi. Mereka sebenarnya biasa digunakan dalam praktek.

Emil Jeřábek

@ EmilJeřábek Mungkin OP sedang berbicara tentang terobosan terbaru David Harvey dan Joris van der Hoeven, "Penggandaan bilangan integer dalam waktu ", yang galaksi (lihat entri blog Lipton ini misalnya: rjlipton .wordpress.com / 2019/03/29 /… )

O (n \log n)

$O(n \log n)$

Lamine

Ketika penulis menulis sendiri (dan disebutkan di blog Lipton), makalah untuk kesederhanaan tidak mencoba untuk mengoptimalkan konstanta, tetapi mereka sangat mungkin dapat dibuat praktis.

Emil Jeřábek

@ EmilJeřábek Makalah itu memang yang saya bicarakan. Makalah ini memang menggambarkan perbaikan yang dapat dilakukan, tetapi sangat meragukan bahwa algoritma seperti ini akan menjadi peningkatan praktis dari algoritma O (n log n log log n) saat ini yang digunakan dalam praktik, mengingat betapa kecilnya log log adalah untuk input praktis.

isaacg

@ EmilJeřábek Secara khusus, algoritma yang disajikan dalam makalah ini menolak algoritma yang lebih sederhana untuk kasus dasar setiap kali jumlahnya kurang dari bit, di mana mereka saat ini mengambil . Optimalisasi yang mereka gambarkan mungkin memungkinkan mereka untuk menggunakan sebagai gantinya, tetapi bit masih melebihi jumlah partikel di alam semesta, sehingga kepraktisan masih keluar dari pertanyaan. Lihat Bagian 5.4 dari makalah mereka.

2^{d^{12}}

$2^{d^{12}}$

d = 1729

$d=1729$

d = 9

$d=9$

2^{9^{12}}

$2^{9^{12}}$

isaacg

$N$ $C_N$

Metodologinya tidak perlu memperbaiki model perhitungan spesifik apa pun, walaupun tentu saja itu bisa berguna. Perhatikan juga bahwa Anda dapat mencoba menghitung perilaku kasus terburuk atau perilaku yang diharapkan, atau masih sesuatu yang lain.

Bahan paling penting dalam metodologi ini adalah analisis fungsi pembangkit nilai-nilai ini. Anda kadang-kadang dapat memperoleh perkiraan asimptotik yang sangat tepat menggunakan metode dari analisis kompleks.

$\mathcal O(n\log n)$

Bahkan, dalam quicksort Anda mengurutkan daftar dengan menyortir sublists secara rekursif, sehingga Anda akan mendapatkan peningkatan untuk semua ukuran jika Anda menggunakan mergesort pada daftar yang lebih kecil dari ukuran 10. Catatan yang menarik dalam buku ini menyebutkan bahwa di beberapa perpustakaan Microsoft yang bersumber terbuka, algoritma pengurutan generik diimplementasikan sebagai quicksort sampai Anda turun ke ukuran 10, setelah itu mergesort digunakan. Dalam komentar kode disebutkan bahwa tes kinerja menunjukkan nilai ini menjadi optimal.

doetoe
sumber

Konstanta Tersembunyi dalam Kompleksitas Algoritma

Jawaban: