Apakah ada masalah yang algoritma yang paling terkenal menjalankan waktu

Saya belum pernah melihat algoritma dengan log di penyebut sebelumnya, dan saya bertanya-tanya apakah ada algoritma yang benar-benar berguna dengan formulir ini?

Saya mengerti banyak hal yang mungkin menyebabkan faktor log dikalikan dalam jangka waktu berjalan, misalnya algoritma pengurutan atau berbasis pohon, tetapi apa yang dapat menyebabkan Anda membaginya dengan faktor log?

Jawaban yang biasa untuk "apa yang bisa menyebabkan Anda membelah dengan log?" adalah kombinasi dari dua hal:

1. model perhitungan di mana operasi aritmatika waktu konstan pada bilangan bulat berukuran kata diperbolehkan, tetapi di mana Anda ingin menjadi konservatif tentang berapa lama kata-kata, sehingga Anda menganggap bit per kata (karena lebih sedikit dari itu dan Anda bahkan tidak bisa mengatasi semua memori, dan juga karena algoritma yang menggunakan pencarian tabel akan memakan waktu terlalu banyak untuk mengatur tabel jika kata-katanya lebih panjang), dan$O(\log n)$
2. sebuah algoritma yang memampatkan data dengan mengemas bit menjadi kata-kata dan kemudian beroperasi pada kata-kata.

Saya pikir ada banyak contoh, tetapi contoh klasik adalah Algoritma Empat Rusia untuk urutan umum terpanjang dll. Ini sebenarnya berakhir menjadi , karena menggunakan ide bit-packing tetapi kemudian menghemat satu detik log factor menggunakan ide lain: mengganti blok operasi bit O ( log 2 n ) dengan pencarian tabel tunggal.$O(n^2/\log^2 n)$$O(\log^2 n)$

Kubus Rubik adalah contoh yang sangat alami (dan bagi saya, tak terduga). Sebuah $n\times n\times n$ kubus memerlukan $\Theta(n^2/\log n)$ langkah untuk memecahkan. (Perhatikan bahwa ini adalah notasi theta, jadi itu adalah batas atas dan bawah yang ketat).

Ini ditunjukkan dalam makalah ini [1].

Mungkin perlu disebutkan bahwa kompleksitas penyelesaian contoh spesifik dari kubus Rubik terbuka, tetapi diperkirakan sebagai NP-hard (dibahas di sini misalnya) NP hard [2]. The $\Theta(n^2/\log n)$ algoritma menjamin solusi, dan menjamin bahwa semua solusi yang asimtotik optimal, tetapi mungkin tidak memecahkan kasus tertentu secara optimal. Definisi Anda tentang kegunaan mungkin atau mungkin tidak berlaku di sini, karena kubus Rubik umumnya tidak diselesaikan dengan algoritma ini (algoritma Kociemba umumnya digunakan untuk kubus kecil karena memberikan solusi cepat dan optimal dalam praktiknya).

[1] Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, dan Andrew Winslow. Algoritma untuk Memecahkan Kubus Rubik. Prosiding Simposium Eropa Tahunan ke-19 tentang Algoritma (ESA 2011), 5-9 September 2011, halaman 689-700

[2] Erik D. Demaine, Sarah Eisenstat, dan Mikhail Rudoy. Memecahkan Rubik's Cube Optimally adalah NP-complete. Prosiding Simposium Internasional ke-35 tentang Aspek Teoritis Ilmu Komputer (STACS 2018), 28 Februari - 3 Maret 2018, halaman 24: 1-24: 13.

Contoh muncul dalam penyebut tanpa trik pengepakan bit adalah sebuah makalah baru-baru ini oleh Agarwal, Ben Avraham, Kaplan dan Sharir pada komputasi jarak Fréchet yang terpisah antara dua rantai poligonal dalam waktu O ( n 2 log log n / log n ) . Meskipun saya tidak terbiasa dengan detail algoritme, satu trik umum adalah mempartisi input menjadi potongan-potongan yang relatif kecil dan kemudian menggabungkan jawaban secara cerdik (tentu saja ini terdengar seperti membagi dan menaklukkan, tetapi Anda tidak mendapatkan log di penyebut dengan beberapa trik pintar)$\log n$$O(n^2\log\log n/\log n)$

Tidak persis seperti yang Anda minta, tetapi situasi "di alam liar" di mana faktor log muncul dalam penyebut adalah kertas " Kerikil dan Program Percabangan untuk Evaluasi Pohon " oleh Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, dan Rahul Santhanam.

Masalah evaluasi pohon (TEP) adalah: diberi pohon -ary yang dianotasi dengan nilai dalam { 1 , ... , k } pada daun dan fungsi { 1 , ... , k } d → { 1 , ... , k } pada node internal , evaluasi pohonnya. Di sini setiap simpul internal mendapatkan nilai fungsi yang dianotasinya pada nilai anak-anaknya. Ini adalah masalah yang mudah, dan intinya adalah untuk menunjukkan bahwa itu tidak dapat diselesaikan dalam ruang logaritmik (ketika ketinggian pohon adalah bagian dari input). Untuk itu, kami tertarik dengan ukuran program percabangan yang menyelesaikan TEP.$d$$\{1,\ldots,k\}$$\{1,\ldots,k\}^d \to \{1,\ldots,k\}$

Dalam Bagian 5, batas-batas ketat disajikan untuk pohon-pohon dengan tinggi 3, baik untuk TEP dan untuk masalah terkait BEP, di mana outputnya diciutkan menjadi dengan cara sewenang-wenang. Untuk TEP batasnya adalah Θ ( k 2 d - 1 ) , sedangkan untuk BEP batasnya adalah Θ ( k 2 d - 1 / log k ) , yaitu Anda mendapatkan penghematan log k .$\{0,1\}$$\Theta(k^{2d-1})$$\Theta(k^{2d-1}/\log k)$$\log k$

Meskipun ini bukan tentang runtime, saya pikir layak menyebutkan hasil klasik dari Hopcroft, Paul, dan Valiant: [1], karena masih dalam semangat "apa yang bisa menyebabkan Anda menyimpan faktor log."$\mathsf{TIME[t]} \subseteq \mathsf{SPACE}[t/\log t]$

Itu memberi banyak contoh masalah yang batas atasnya paling dikenal dalam kompleksitas ruang memiliki log dalam penyebut. (Tergantung pada sudut pandang Anda, saya akan berpikir bahwa membuat contoh ini sangat menarik - teorema yang menakjubkan! - atau sangat tidak menarik - mungkin tidak "benar-benar berguna".)

[1] Hopcroft, Paul, dan Valiant. Tepat waktu versus ruang . J. ACM 24 (2): 332-337, 1977.

Ada dua masalah dengan kompleksitas kueri yang ketat :$\Theta(n/\log n)$

• Masalah penimbangan koin dengan skala pegas.
• Mastermind dengan posisi n dan 2 warna.

Algoritma yang paling dikenal untuk menghitung jarak edit (alias Levenshtein) antara dua string dengan panjang membutuhkan waktu O ( ( n / log n ) 2 ) :$n$$O((n/\log n)^2)$

William J. Masek, Mike Paterson: A String Algoritma Komputasi Edit Lebih Jauh. J. Comput. Syst. Sci. 20 (1): 18-31 (1980).

muncul sebagai batas yang benar untuk masalah yang dipertimbangkan oleh Greg dan Paul Valiant (tidak ada koneksi ke trik bit):$\Theta(n/\log n)$

Gregory Valiant, dan Paul Valiant, The Power of estimators linier, 2011. Dalam Simposium IEEE Tahunan ke-52 tentang Yayasan Ilmu Komputer, FOCS 2011.

Berikut adalah contoh lain dari ikatan ketat yang memiliki faktor log. (Ini adalah Teorema 6.17 dari Kompleksitas Fungsi Boolean: Kemajuan dan Batas oleh Stasys Jukna.)

$\Theta(n^2/\log n)$$n$

$m$$\text{poly}(m)$$n := O(m \log m)$$O(\log m)$ bits. So an upper bound that looks natural in terms of $m$, like $\Theta(m^2 \log m)$, becomes $\Theta(n^2/\log n)$ when expressed in terms of $n$, where $n$ is the number of bits in the input.

Finding the prime factors of n by trial division when the list of primes is already given. There are $\theta(\frac{n}{\log(n)})$ primes less than n so if these primes are given to you, then trial division of n by each of them takes $\theta(\frac{n}{\log(n)})$ time (assuming division is a constant-time operation)

somewhat similar to JG's answer & "thinking outside the box", this seems like a related/relevant/apropos/fundamental negative result. based on diagonalization with a universal TM, there exists a $O(f(n))$ DTIME language that cannot run in $O\left({f(n)\over{\log f(n)}}\right)$ DTIME, due to the time hierarchy theorem. so this applies to a linear DTIME algorithm that exists, $f(n)=n$, that runs impossibly in $O\left(n \over {\log n} \right)$ DTIME.