Kompleksitas waktu dari suatu algoritma: Apakah penting untuk menyatakan dasar logaritma?

Karena hanya ada konstanta di antara basis logaritma, bukankah tidak apa-apa untuk menulis $f(n) = \Omega(\log{n})$ , yang bertentangan dengan $\Omega(\log_2{n})$ , atau apa pun basisnya?

Itu tergantung di mana logaritma. Jika itu hanya faktor, maka itu tidak membuat perbedaan, karena big-O atau $\theta$ memungkinkan Anda untuk mengalikan dengan konstanta apa pun.

Jika Anda mengambil $O(2^{\log n})$ maka pangkalan itu penting. Dalam basis 2 Anda hanya akan memiliki $O(n)$ , dalam basis 10 ini tentang $O(n^{0.3010})$ .

Karena notasi asymptotic adalah menyadari faktor konstan, dan dua logaritma berbeda dengan faktor konstan, dasar tidak ada bedanya: $\log_a n = \Theta(\log_b n)$ untuk semua $a,b > 1$ . Jadi tidak perlu menentukan basis logaritma saat menggunakan notasi asimptotik.

Sebagai $\log_xy = \frac{1}{\log_y{x}}$ dan$\log_x{y} = \frac{\log_z{y}}{\log_z{x}}$ , jadi $\frac{\log_a{n}}{\log_b{n}} = \frac{\log_n{b}}{\log_n{a}} = \log_a{b}$. Karena$\log_a{b}$adalah konstanta positif (untuk semua$a,b > 1$), maka$\log_a{n} = \Theta(\log_b{n})$.

Dalam kebanyakan kasus, aman untuk menjatuhkan basis logaritma karena, seperti jawaban lain menunjukkan, rumus perubahan-basis untuk logaritma berarti bahwa semua logaritma adalah kelipatan konstan satu sama lain.

Ada beberapa kasus di mana ini tidak aman untuk dilakukan. Sebagai contoh, @ gnasher729 telah menunjukkan bahwa jika Anda memiliki logaritma dalam eksponen, maka basis logaritmik memang signifikan.

Saya ingin menunjukkan kasus lain di mana basis logaritma signifikan, dan itu adalah kasus di mana basis logaritma tergantung langsung pada parameter yang ditentukan sebagai input ke masalah. Sebagai contoh, algoritma radix sort bekerja dengan menuliskan angka dalam beberapa basis $b$ , membusuk nomor masukan ke dasar- mereka $b$ angka, kemudian menggunakan penghitungan sort untuk mengurutkan angka-angka satu digit pada suatu waktu. Pekerjaan yang dilakukan per putaran adalah $\Theta(n + b)$ dan ada kira-kira $\log_b U$ putaran U (di mana $U$ adalah bilangan bulat input maksimum), sehingga total runtime adalah $O((n + b) \log_b U)$ . Untuk bilangan bulat tetap$b$ ini disederhanakan menjadi$O(n \log U)$ . Namun, apa yang terjadi jika$b$ bukan konstanta? Teknik yang cerdas adalah memilih$b = n$ , dalam hal ini runtime disederhanakan menjadi$O(n + \log_n U)$ . Sejak$\log_n U$ =$\frac{\log U}{\log n}$ , ekspresi keseluruhan disederhanakan menjadi$O(\frac{n \log U}{\log n})$. Perhatikan bahwa, dalam kasus ini, basis logaritma memang signifikan karena tidak konstan sehubungan dengan ukuran input. Ada algoritma lain yang memiliki runtimes yang sama (analisis lama hutan disjoint-set berakhir dengan istilah$\log_{m/2 + 2}$suatu tempat, misalnya), dalam hal menjatuhkan basis log akan mengganggu analisis runtime.

Kasus lain di mana basis log penting adalah di mana ada beberapa parameter eksternal yang dapat disesuaikan dengan algoritma yang mengontrol basis logaritmik. Contoh yang bagus untuk hal ini adalah B-tree, yang membutuhkan beberapa parameter eksternal $b$ . Ketinggian pohon-B orde $b$ adalah $\Theta(\log_b n)$ , di mana pangkal logaritma signifikan karena $b$ bukan konstanta.

Untuk meringkas, dalam kasus di mana Anda memiliki logaritma dengan basis konstan, Anda biasanya dapat (dengan pengecualian seperti apa yang ditunjukkan oleh @ gnasher729) jatuhkan basis logaritma. Tetapi ketika basis logaritma tergantung pada beberapa parameter pada algoritma, biasanya tidak aman untuk melakukannya.