Discussion :

[snipes]

salut tout le monde
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

[ToTo13]

Bonjour,

je n'ai pas de cours sous la main, est mon amis dans ce cas là.
Juste une petite précision :

O(n) = nlogn

Soit la compléxité est en O(n), soit en O(n log(n), il ne peut y avoir d'égalité.

[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

[pseudocode]

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

?

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é.

[snipes]

lol je me suis mal exprimé sur ce coup la j avoue
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)

[pseudocode]

en fait je voulais dire que ca ne me dit pas a quel moment c'est nlogn ou logn etc

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.

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...