Complexité d un algorithme

Complexité d'un algorithme

> Tutoriel LeekScript

Idée générale

Pour estimer la quantité d'opérations qu'une fonction ou un algorithme va consommer, il est utile d'avoir une idée du rapport entre la taille des arguments qu'on lui donne, ou la taille d'un paramètre, et le nombre maximal d'opérations effectuées. C'est ce qu'on appelle la complexité algorithmique.

Commençons par un exemple simple : une boucle for.

for (var i=0; i N, on ait f(n) n² croît beaucoup moins vite que la fonction n -> 4^n : lorsque les MPs augmentent, une fonction de cases accessibles mal codée se mettra à coûter excessivement cher, alors qu'une même fonction bien codée gardera un coût raisonnable.

Calcul pratique

La question naturelle qu'on peut alors se poser est : comment calculer ces O, et quelles sont les fonctions intéressantes avec lesquelles on peut comparer notre code ? Je vais donc donner quelques complexités qu'on retrouve régulièrement, en les classant de la plus faible à la plus forte, et des règles de calcul pour évaluer la complexité d'un algorithme. Il faudra ensuite combiner ces règles pour trouver la complexité d'un morceau de code donné !

Hiérarchie

--- Les complexités que l'on retrouvera souvent sont les suivantes, dans l'ordre ascendant :

O(1) : "complexité constante" O(n) : "complexité linéaire" O(n log(n)) : "complexité quasi-linéaire" O(n²) : "complexité quadratique" O(n^k) avec k entier : "complexité polynomiale" O(k^n) : "complexité exponentielle" O(n!) : "complexité factorielle (on peut montrer que c'est la même chose que O(sqrt(2πn)(n/e)^n))"

Règles de calcul

--- // code de coût O(g(n)), puis // code de coût O(h(n))

Quand on a deux blocs de code qui se suivent, on garde le terme "le plus grand" : si g est une complexité supérieure à h, alors le code est en O(g(n)). Si h est une complexité supérieure à g, alors le code est en O(h(n)). Si les deux morceaux de code ont la même complexité, le bloc entier a la même complexité.

On a vu sur des exemples comment se comportent les boucles for :

for (var i=0; i 1), elle commence par calculer les combos avec n-1 éléments, puis pour chaque combo trouvée elle en ajoute 2 à la liste qu'elle renvoie finalement (une copie de la combo, et une copie de la combo plus le premier élément de la liste). Ainsi, si on note N(n) le nombre d'éléments dans la liste des combos renvoyées avec une liste de n éléments en entrée, on a N(n) = 2*N(n-1) pour n > 1. De plus, on a N(1) = 2 puisque si la liste ne contient qu'un élément, on renvoie une liste contenant 2 combos. Ainsi, par récurrence, on obtient N(n)=2^n. Or si on a 2^n éléments au final, c'est qu'on a fait 2^n push. On pourrait aussi compter le nombre d'appels de fonctions, de count, etc. : on n'en fait pas plus que de push. Ainsi, on a une fonction de complexité O(2^n).

L'idée, pour étudier la complexité d'une fonction récursive, est ainsi de trouver une formule de récurrence. Celle-ci était particulièrement simple, on peut avoir affaire à des choses bien plus tordues !

Fonctions du Leekscript

--- Je vais enfin lister quelques fonctions du leekscript entraînant un coût dépendant de l'entrée (liste non-exhaustive). Si la fonction que vous cherchez n'apparaît pas, faites des tests ou demandez sur le chat !

Fonctions sur les tableaux : n est la taille du tableau

Fonction | Coût ---------|----- arrayFilter | O(n) arrayFoldLeft | O(n) arrayFoldRight | O(n) arrayIter | O(n) arrayMap | O(n) arrayMax | O(n) arrayMin | O(1) (oui, c'est absurde que le min et le max ne coûtent pas la même chose...) arrayPartition | O(n) arraySort | O(n log(n)) assocSort | O(n log(n)) average | O(n) fill | je ne sais pas (redimensionnement de tableaux caché derrière) inArray | O(n) join | euh... Là, je sais pas. keySort | O(n log(n)) pop et push | je ne sais pas (redimensionnement de tableaux caché derrière) remove | ? removeElement | ? removeKey | ? reverse | O(n) search | O(n) shift et unshift | je ne sais pas (redimensionnement de tableaux caché derrière) shuffle | O(n), en théorie. Mais le shuffle de LW est louche, il coûte moins de n sur de grands tableaux... sort | O(n log(n)) sum | O(n)

Fonctions de déplacement et de distances : n est le nombre de MP entre le départ et l'arrivée

Fonction | Coût ---------|----- getPath | O(n²) (probablement, je ne connais pas le code exact) getPathLength | O(n²) (même remarque)