Complexité logarithmique
clic
-
clic -
clic -
Bonjour,
J'aimerais un exemple d'algorithme avec complexité logarithmique qui n'est pas la recherche dichotomique,c'est pour me permettre de mieux comprendre cette classe de complexité.
Merci d'avance!
J'aimerais un exemple d'algorithme avec complexité logarithmique qui n'est pas la recherche dichotomique,c'est pour me permettre de mieux comprendre cette classe de complexité.
Merci d'avance!
1 réponse
-
Bonjour,
Avec une complexité logarithmique O(log n), même si elle est un peu cachée ce sera toujours plus ou moins de la dichotomie.
Tu peux par exemple t'intéresser à la puissance p^n d'un nombre en te basant sur l'égalité p^(2k)=(p^k)². Le nombre de multiplications effectuées est logarithmique par rapport à l'exposant n.
