Au sujet de la notation de la complexité

Bonjour, pouvez vous m'éclairer sur mon petit problème, je ne sait jamais quel logarithme utilisé celui en base 10 ou en base 2. Par exemple dans l'expression de la par complexité de prim : m + n lg(n) (formule prise sous wikipédia) lg signifie log en base 10 ou log en base 2 ?

On parle souvent de 'diviser pour régner' (divide and conquer) ce qui fait que ton logarithme est un logarithme en base 2 ;)

Citation:

---

Envoyé par amateurc

Bonjour, pouvez vous m'éclairer sur mon petit problème, je ne sait jamais quel logarithme utilisé celui en base 10 ou en base 2. Par exemple dans l'expression de la par complexité de prim : m + n lg(n) (formule prise sous wikipédia) lg signifie log en base 10 ou log en base 2 ?

---

En terme de complexité ca n'a généralement pas trop d'importance :

Log_baseK (x) = Ln(x)/Ln(K) = Cste . Ln(x)

donc on a :

Log_baseK (x) = Θ(Ln(x)) (theta de Ln(x))

et donc

Log_baseK (x) = O(Ln(x)) (grand O de Ln(x))

merci beaucoup de vos explications