Bonjour,
Dans les exercices, devons nous considérer que la fonction qui renvoie la taille d'une liste est de complexité constante ou bien de complexité linéaire ?
Merci beaucoup
Bonjour !
Pour la complexité d'un algorithme, on doit considérer le grand O du nombre d'opérations effectuées pour une tâche donnée, sachant que nous regardons le pire cas possible. Quand la longueur (de la liste par exemple) tend vers l'infini, le grand O est la partie de la fonction qui croît le plus vite (dans l'ordre e(x), les polynômes, logx*x, x et logx). Je n'ai pas vu dans la série de complexité dans laquelle on doit considérer la complexité de la taille. En effet, la complexité des algorithmes est toujours de la forme f(x) +taille(x), avec f un terme dominant par rapport à taille. Du coup, la complexité de la taille ne change rien. Mais peut être ai je mal regardé ! Quel exercice selon vous présente cette difficulté ?
Bonjour,
Je n'ai pas vu ce cas dans un exercice en particulier, je me demandais juste par principe.
Je n'ai pas vu ce cas dans un exercice en particulier, je me demandais juste par principe.
C'est une très bonne question et la réponse de M. Protais reste valable aussi dans le cas général :
- l'algorithme taille() est toujours O(n) : ATTENTION !!! Lisez moi bien : je n'ai pas dit qu'il n'était pas O(1) !! Rappel : O(1) est INCLUS dans O(n) : O(n) veut dire « au pire comme "c fois n" » ;
donc, dans tous les cas où ce O(n) suffit pour conclure et ne change pas la conclusion (p.ex. parce que la complexité finale globale de l'algorithme étudié est plus grande que O(n)), il n'y a rien à dire : on s'attend à ce que vous sachiez que taille est en O(n) ; - pour les cas où le fait qu'il soit « en O(n) mais pas en O(1) » ou qu'il soit en O(1) fait une différence, alors vous pouvez supposer qu'il est en O(1), mais il faudra le dire explicitement pour montrer que vous avez vu le problème
(ou alors, évidemment, si c'est clairement demandé, faire la distinction et le calcul dans les deux cas, comme nous l'avons fait en cours ; mais ce sera plus rare et, comme dit, explicitement demandé).