Complexité
Fermé
dx3d
Messages postés
68
Date d'inscription
dimanche 6 septembre 2009
Statut
Membre
Dernière intervention
19 juillet 2017
-
20 juin 2014 à 19:19
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 20 juin 2014 à 19:22
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 20 juin 2014 à 19:22
A voir également:
- Ce mot de passe ne répond pas aux critères de longueur, de complexité, de date ou d'historique de la stratégie de mot de passe de votre entreprise.
- Voir mot de passe wifi android - Guide
- Trousseau mot de passe iphone - Guide
- Mot de passe administrateur - Guide
- Identifiant et mot de passe - Guide
- Réinitialiser pc sans mot de passe - Guide
1 réponse
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
20 juin 2014 à 19:22
20 juin 2014 à 19:22
Bonjour,
Un exemple de O(log n) c'est le parcours par dichotomie.
Tu pars du milieu, si c'est moins, tu vas à gauche, si c'est plus tu vas à droite.
Ta recherche se divise par 2 à chaque fois, si bien que si n=2^k au départ, à l'étape suivant tu n'auras plus que 2^(k-1)... jusqu'à avoir k=0, soit k étapes.
Or si n=2^k alors k=log2(n), CQFD.
Un exemple de O(log n) c'est le parcours par dichotomie.
Tu pars du milieu, si c'est moins, tu vas à gauche, si c'est plus tu vas à droite.
Ta recherche se divise par 2 à chaque fois, si bien que si n=2^k au départ, à l'étape suivant tu n'auras plus que 2^(k-1)... jusqu'à avoir k=0, soit k étapes.
Or si n=2^k alors k=log2(n), CQFD.