Version imprimable
salut tout le monde :yaisse2:
je suis a la recherche de cours et/ou exercices (avec le corrigé biensur) concernant le calcul de la complexité d'un algorithme (complexité en temps et en memoire)
enfin plus des exercices quand meme ou des exemples expliquant à quel moment on dit que le complexité est egale : O(n) = nlogn ou encore logn ou 2^n etc
je m y perd un petit peu
tout aide est la bienvenue
merc d'avance ;)
Bonjour,
je n'ai pas de cours sous la main, :google: est mon amis dans ce cas là.
Juste une petite précision :
Soit la compléxité est en O(n), soit en O(n log(n), il ne peut y avoir d'égalité.Citation:
Envoyé par snipes
ben justement j ai cherché sur google et je trouve des cours qui m'indique uniquement ce que ca signifie mais ca ne me dit pas a quel moment je dois l appliquer :?
8O ?Citation:
Envoyé par snipes
La complexité est juste un indicateur pour juger de la performance d'un algorithme (performance mémoire, ou cpu, ou ...), par exemple pour faire des comparaisons avec d'autres algos.
Si tu n'as pas besoin de juger/comparer la performance de ton algo, inutile de calculer sa complexité.
lol :mouarf: je me suis mal exprimé sur ce coup la j avoue :lol:
en fait je voulais dire que ca ne me dit pas a quel moment c'est nlogn ou logn etc
pour ca que je demandais quelques exemples (differents cas si possible) me permettant de voir comment c'est calculé car moi je trouve toujours 0(n) ou 0(n^2 ou 3)
Généralement les log() apparaissent quand ont fait des dichotomies, c'est a dire souvent dans les algos recursifs du style: on sépare les donnés en 2 et on recommence.Citation:
Envoyé par snipes
Par exemple, la recherche dans une liste triée: Tu prend l'élément au milieu de la liste, et si ce n'est pas le bon tu refais une recherche sur la sous-liste de gauche ou droite (qui est donc moitié moins grande)
Le nombre de comparaison a faire pour une liste triée de taille n est donc:
C(n) = 1 + C(n/2)
(la comparaison de l'élément du milieu + la/les comparaisons de la sous liste)
Il suffit de trouver le terme générale de cette suite. Grace a un surpuissant changement de variable n=2^t on obtient:
C(2^t) = 1 + C(2^t/2) = 1 + C(2^(t-1))
et par recurrence:
C(2^t) = 1 + C(2^(t-1)) = 1 + 1 + C(2^(t-2)) = 1 + 1 + 1 + C(2^(t-3)) = ...
C(2^t) = t + C(2^0) = t + constante
donc C(2^t) = O(t)
et avec le changement de variable inverse:
C(n) = log(n)/log(2) = O(log(n))
Bref, c'est que des maths... :aie: