Complexité
dx3d
Messages postés
72
Statut
Membre
-
KX Messages postés 19031 Statut Modérateur -
KX Messages postés 19031 Statut Modérateur -
Bonjour, je rencontre depuis toujours un problème pour le calcul de la complexité, surement du fait que je n'ai pas porté assez attention durant le cours et depuis je n'y ai pas trop pensé, j'aimerais maintenant combler mes lacunes.
Donc si je comprend bien jusque là quand on demande d'écrire une fonction qui s'exécute en temps O(1) aucune boucle ne doit être utilisé et toutes les instructions doivent être basiques.
En O(n) une seule boucle est autorisé. Et O(n^k) autorise k nombre de boucles.
Cependant il m'arrive de trouvé des complexités tels que O(log(n)) et d'autres du genre, dans quelle cas à t'on ce genre de complexité ?
Merci de m'éclairer ! :)
PS : Si j'ai tout faux il suffit de me le dire, j'irais revoir le cours en sa totalité.
Donc si je comprend bien jusque là quand on demande d'écrire une fonction qui s'exécute en temps O(1) aucune boucle ne doit être utilisé et toutes les instructions doivent être basiques.
En O(n) une seule boucle est autorisé. Et O(n^k) autorise k nombre de boucles.
Cependant il m'arrive de trouvé des complexités tels que O(log(n)) et d'autres du genre, dans quelle cas à t'on ce genre de complexité ?
Merci de m'éclairer ! :)
PS : Si j'ai tout faux il suffit de me le dire, j'irais revoir le cours en sa totalité.
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.
- Trousseau mot de passe iphone - Guide
- Mot de passe - Guide
- Mot de passe administrateur - Guide
- Mot de passe bios perdu - Guide
- Voir mot de passe wifi android - Guide
1 réponse
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.
