Complexité temporelle d'un algorithme: est-il important d'énoncer la base du logarithme?

Puisqu'il n'y a qu'une constante entre les bases des logarithmes, n'est-ce pas juste d'écrire $f(n) = \Omega(\log{n})$ , par opposition à $\Omega(\log_2{n})$ , ou quelle que soit la base?

Cela dépend où se trouve le logarithme. Si ce n'est qu'un facteur, cela ne fait aucune différence, car big-O ou $\theta$ vous permet de multiplier par n'importe quelle constante.

Si vous prenez $O(2^{\log n})$ la base est importante. Dans la base 2, vous auriez juste $O(n)$ , dans la base 10, c'est environ $O(n^{0.3010})$ .

Parce que la notation asymptotique est inconsciente des facteurs constants et que deux logarithmes différents diffèrent par un facteur constant, la base ne fait aucune différence: $\log_a n = \Theta(\log_b n)$ pour tout $a,b > 1$ . Il n'est donc pas nécessaire de spécifier la base d'un logarithme lors de l'utilisation de la notation asymptotique.

Comme $\log_xy = \frac{1}{\log_y{x}}$ et$\log_x{y} = \frac{\log_z{y}}{\log_z{x}}$ , donc $\frac{\log_a{n}}{\log_b{n}} = \frac{\log_n{b}}{\log_n{a}} = \log_a{b}$. Comme$\log_a{b}$est une constante positive (pour tout$a,b > 1$), alors$\log_a{n} = \Theta(\log_b{n})$.

Dans la plupart des cas, il est prudent de supprimer la base du logarithme car, comme d'autres réponses l'ont souligné, la formule de changement de base des logarithmes signifie que tous les logarithmes sont des multiples constants les uns des autres.

Dans certains cas, cela n'est pas sûr. Par exemple, @ gnasher729 a souligné que si vous avez un logarithme dans un exposant, alors la base logarithmique est en effet significative.

Je voulais souligner un autre cas où la base du logarithme est significative, et c'est des cas où la base du logarithme dépend directement d'un paramètre spécifié en entrée du problème. Par exemple, l'algorithme de tri radix fonctionne en écrivant des nombres dans une base $b$ , en décomposant les nombres d'entrée en leurs chiffres de base $b$ , puis en utilisant le tri par comptage pour trier ces nombres un chiffre à la fois. Le travail effectué par tour est alors $\Theta(n + b)$ et il y a à peu près $\log_b U$ tours (où $U$ est l'entier d'entrée maximum), donc le temps d'exécution total est $O((n + b) \log_b U)$$b$$O(n \log U)$$b$$b = n$$O(n + \log_n U)$$\log_n U$$\frac{\log U}{\log n}$$O(\frac{n \log U}{\log n})$$\log_{m/2 + 2}$

$b$$b$$\Theta(\log_b n)$$b$

Pour résumer, dans le cas où vous avez un logarithme à base constante, vous pouvez généralement (sous réserve d'exceptions comme ce que @ gnasher729 a signalé) supprimer la base du logarithme. Mais lorsque la base du logarithme dépend de certains paramètres de l'algorithme, il n'est généralement pas sûr de le faire.