Complexité et fonctions récursives

> Tutoriel LeekScript

Avertissement : Cet article est à fort contenu mathématique (du moins pour ce wiki). Ne pas utiliser sans avis médical.

Plus sérieusement : je vais ici essayer de parler de la L'Optimisation des fonctions récursives (La_Récursivité). Cet article est plutôt destiné à des gens qui s'intéressent à la programmation fonctionnelle et à la théorie de la programmation.

Il n'est pas toujours facile, quand on écrit une fonction récursive, de savoir combien d'appels on va faire avant d'arriver au résultat. Ni même si on va arriver au résultat, parfois. Le tutoriel sur La_Récursivité donne des pistes d'optimisation des fonctions récursives, mais ne fait pas d'étude de complexité ni de correction ; je vais donc ici illustrer par des exemples quelques méthodes pour s'y retrouver.

Cette liste d'exemples n'a pas vocation à être exhaustive, il faudra pour chacun de vos algorithmes examiner précisément les opérations effectuées.

A vous ensuite de copier ces idées pour vos algorithmes personnels, et si vous trouvez d'autres exemples valant la peine d'être mentionnés, de les expliquer ici !

Premiers exemples

Certaines fonctions récursives simples ont une complexité facile à étudier. C'est le cas du premier exemple du tutoriel sur la récursivité :

function sumN(n) { if (n === 0) { return 0; } else { return n + sumN(n - 1); } }

Ici, c'est assez simple : on voit facilement que si on donne un entier n (positif !) à cette fonction, elle va ajouter n à la somme de 0 à n-1, qu'elle calcule en s'appelant elle-même. Donc on va faire n + (n-1 + ... + (0)...), ce qui fait n additions et n appels de fonctions, soit une complexité en O(n).

Cependant, si on donne en entrée un entier négatif, cette fonction va causer un stack overflow : elle va additionner des nombres négatifs sans jamais atteindre 0. De même, si on donne un nombre non-entier, on n'atteindra jamais 0 en soustrayant 1 plusieurs fois. Attention donc à la '''correction''' de vos fonctions récursives : si vous n'avez pas prévu tous les cas ou si vous les utilisez avec une entrée ne correspondant pas à ce que vous aviez en tête en la codant, vous pourriez avoir de mauvaises surprises.

Le tutoriel sur l'optimisation donne lui l'exemple d'une fonction de complexité O(2^n) :

function getAllCombos(liste_items){ var nb_items = count(liste_items);

if(nb_items == 1) { return [[], liste_items]; }

var sous_liste = subArray(liste_items, 1, nb_items - 1); var liste_combos_partielles = getAllCombos(sous_liste); // Appel récursif var m = count(liste_combos_partielles);

//On duplique ensuite la liste des combos : on garde celles qu'on avait, et on ajoute les mêmes avec le premier élément de liste_items for(var i=0; i P(n) = 2*P(n-1). Comme on a de plus P(1) = 2, on obtient la formule P(n) = 2 * ... * 2 = 2^n, d'où la complexité (au moins) exponentielle. On peut alors montrer que cette fonction a bien une complexité exponentielle (et pas plus grande) : chaque appel de la fonction crée un tableau de taille n-1 avec subArray (coût : O(n)), puis fait m pushs avec m la taille du tableau de combos partielles, soit 2^(n-1) (coût : K * 2^(n-1) avec K le coût de push), ce qui écrase le coût du subArray, et amène ainsi à une complexité déterminée par le nombre P(n) de push effectués.

C'est cette idée que je vais ici développer : obtenir une formule de récurrence et essayer d'en déduire une formule pour majorer le nombre d'appels, pour enfin en déduire la complexité en étudiant ce que fait la fonction en plus de ses appels récursifs. Je ne parlerai plus tellement de correction (sauf à la toute fin), mais gardez la notion en tête...

Dans toute la suite, C(n) désignera le coût de la fonction étudiée.

Récurrences simples : C(n) = f(C(n-1))

Le mot "simple" ne veut pas dire ici que la complexité va être gentille, ni forcément facile à calculer. Il veut dire que l'on a une récurrence d'ordre 1, c'est-à-dire une expression donnant C(n) en fonction de C(n-1).

Somme des puissances : récurrence de la forme C(n) = a * C(n-1) + b

Commençons doucement. Le premier exemple que je vais étudier est passablement idiot, mais il me sert aussi à introduire mon formalisme. Vous n'apprendrez rien de fou sur la complexité ici, mais au moins les cas simples seront traités dans cette page.

Reprenons une fonction très simple (et inutile, et passablement mal écrite puisqu'elle utilise deux fois le même appel de fonction, mais il me fallait un exemple simple) :

function sumPowers(n , k) { //n entier, k quelconque if (n === 0) { return 0; } else { return n**k + (sumPowers(n - 1 , k) + sumPowers(n - 1 , k))/2; } }

Le coût C(n) est ici étudié en fonction du seul entier n, puisque l'exponentiation a un coût fixe en leekscript. Pour le coût en fonction de la taille de l'entrée, c'est-à-dire du nombre de bits de n, il faudrait ajouter une exponentielle dans les complexités. Mais le but est ici d'étudier les suites C(n) = a * C(n-1) + b, je vais donc m'en tenir à la complexité en fonction de n et non de son nombre de bits.

Cette fonction ressemble beaucoup à la première étudiée, mais en plus de faire une addition elle calcule une puissance au passage. En Leekscript, l'opérateur * coûte 140 opérations (tout comme la fonction pow), l'addition et la soustraction coûtent 1, la division coûte 5, le if coûte 1, la comparaison n === 0 coûte 1 et l'appel de fonction avec deux arguments coûte 5. La fonction de coût C(n) vérifie donc C(n) = 161 + 2C(n-1) pour tout n>0, et C(0)= 2.

Maintenant, demandons nous comment on peut estimer le coût à partir de là. On a une suite définie par une formule C(n) = a C(n-1)+ b et C(0) = c, avec a ≠ 1. L'idée va être de se ramener à la forme, plus facile à utiliser, u(n) = a u(n-1). Pour ça, posons u(n)=C(n) + b/(a-1). On peut alors écrire :

C(n) = a C(n-1) + b ⇒ C(n) = a C(n-1) + (a-1)b/(a-1) ⇒ C(n) = a C(n-1) + ab/(a-1) - b/(a-1) ⇒ C(n) + b/(a-1) = a C(n-1) + a*b/(a-1) ⇒ u(n) = a u(n-1)

On a ainsi pour tout n >= 0 :

u(n) = a^n u(0)

De plus, u(0) est facile à calculer : u(0) = C(0) + b/(a-1) = c + b/(a-1). On peut donc en déduire la valeur de u(n) pour tout n : u(n) = a^n * (c + b/(a-1)). En reprenant la définition de u(n) à partir de C(n), on obtient :

C(n) = u(n) - b/(a-1) = a^n * (c + b/(a-1)) - b/(a-1)

On ne peut pas dire que la formule soit très jolie, mais que nous apprend-elle ? Eh bien, que le coût est en O(a^n) : b et c disparaissent dans des constantes (multiplicatives et additives). Cette fonction a un coût exponentiel de base a, qui vaut ici 2. On aurait pu s'en douter : ce qui va coûter cher, finalement, ce n'est pas de calculer les puissances avec , mais de recalculer plein de fois les mêmes choses de façon idiote. **Moralité : Quand vous avez une fonction récursive, ne recalculez jamais ce qui n'est pas nécessaire !

Et si on avait été malin et qu'on avait évité de recalculer ?

function sumPowers(n , k) { //n entier, k quelconque if (n === 0) { return 0; } else { return n**k + sumPowers(n - 1 , k); } }

On aurait eu, cette fois, C(n) = 149 + C(n-1). On obtient donc le cas, non traité par ce qui précède, où a = 1.

Et ce cas est nettement plus simple : par une récurrence directe, on obtient C(n) = 149n + C(0) = 149n + 2, d'où une complexité linéaire, avec une constante donnée par le coût des opérations effectuées dans la boucle.

Déterminant de matrices (très mauvaise méthode) : récurrence non-linéair

Si vous avez fait un peu de maths, vous savez probablement ce que sont les matrices : des tableaux de nombres, avec des lois d'addition, de multiplication par un élément du corps de base (on va dire ℝ, ici) et de multiplication entre elles. On va s'intéresser au calcul du déterminant des matrices carrées, un outil assez utile pour les étudier. Une façon de calculer ce déterminant est la suivante :

function det(M){ //entrée M : matrice carrée de taille n sous la forme d'un tableau de taille n, contenant des tableaux de taille n, contenants des nombres. var n = count(M); if(n === 1) { return M[0][0]; // Si la matrice est de taille 1, son déterminant est égal à sa seule valeur } else { //Sinon... var output = 0; var firstLine = shift(M);// ...on prend la première ligne... for(var i=0; iC en fonction du nombre de lignes de la matrice (ou du nombre de colonnes, c'est pareil puisque j'ai pris des matrices carrées).

Coût pour n = 1 : pas grand chose, quelques opérations (nb : count est en temps constant en leekscript). Coût pour n > 1 :

divers petits coûts fixes
1 fois shift, qui est en O(n) (je crois)
n² fois remove, qui doit aussi être en O(n)
n appels à la fonction det sur une entrée de taille n-1.

On a donc quelque chose de la forme C(n) = n * C(n-1) + a * n^3 + des petits trucs.

Disons déjà quelque chose : on a C(n) > n * C(n-1). On en déduit aisément que la complexité de ce truc est au moins de O(n!).

On peut également, dans l'autre sens, majorer : C(n) ⩽ n * C(n-1) + b * n^3 pour un nombre b supérieur à a (et n assez grand). Étudions la suite définie par u(n) = n * u(n-1) + b * n^3 (pour n>1) et u(1)=1 (u(1) ne vaut pas 1, mais ça ne changera pas la complexité, juste la constante cachée par le O). Par récurrence, on a :

!Suite_rec_determinant_matrices

La série des i^2/((i-1)!) converge bien vers une limite finie. Donc on obtient u(n) ⩽ k * n! avec k un certain réel. Donc C(n) est au plus de complexité O(n!). Avec ce qu'on avait avant, on conclut que C(n) est de complexité O(n!).

Cette idée de chercher à '''comparer''' au lieu de mettre une égalité s'avère souvent utile : après tout, on cherche un O(f(n)), pas une estimation précise, et si on peut dire que la complexité est "au moins ça" pour dire qu'une fonction est coûteuse, ou "au pire ça" pour dire qu'elle est peu coûteuse, c'est déjà intéressant !

Récurrences de type C(n) = f(C(n/a)) avec a un nombre fixé

Ces récurrences apparaissent naturellement lors d'utilisation de la méthode de dichotomie, ou d'algorithmes de type diviser pour régner. Elles donnent des complexités avec des logarithmes en général.

Recherche dichotomique dans un tableau trié

Le leekscript est doté d'une fonction de recherche dans un tableau. Néanmoins, si on sait que le tableau est trié (parce qu'on l'a trié avant, ou qu'il est trié par construction), il y a moyen d'effectuer une recherche plus rapidement qu'avec ladite fonction :

On va donc faire au plus log(n) étapes. Comme à chaque fois on ajoute un coût de a, le coût de cette fonction est de a*log(n). La complexité de cet algorithme est ainsi de O(log(n)) (ou, pour ceux qui se poseraient la question, O(ln(n)) : les logarithmes sont proportionnels entre eux).

Attention cependant : ce n'est pas pour autant qu'il faut trier tous vos tableaux systématiquement. Si le coût de la recherche est ainsi réduit, le coût de tri est lui en O(n log(n)), soit plus que le coût de la recherche par la fonction native du leekscript. Si vous avez beaucoup de recherches à faire dans un tableau, le trier avant peut être une bonne idée, si vous n'en avez que quelques unes, certainement pas.

Tri fusion

L'algorithme de tri fusion est un algorithme de tri (comme son nom l'indique) d'un tableau. Il existe des versions consommant moins d'espace mémoire, mais elles sont un peu plus compliquées à mettre en œuvre que ce que je vais vous proposer ci-dessous. Comme pour tout algorithme de tri, on ne peut pas espérer une meilleure complexité en temps que O(n log(n)).

Cet algorithme repose sur le principe suivant : si le tableau est de taille 1, il est forcément trié. Sinon, on sépare le tableau en deux, on trie chaque moitié, et on fusionne les deux tableaux pour obtenir un tableau trié.

// Fonction permettant de fusionner deux tableaux triés en gardant l'ordre function fusion(@array1, @array2){ //Entrée : deux tableaux triés var output = []; var l = count(array1), m = count(array2); var i = 0, j=0; //i et j vont servir à stocker l'avancée progressive dans chacun des tableaux while(i+j 1) deux fusionSort avec une entrée de taille deux fois plus petite et une fusion des deux tableaux résultants. Commençons par regarder le coût de fusion. La fonction fusion est principalement composée d'un gros while sur la somme des tailles des tableaux donnés en entrée. Sa complexité va donc être de O(l+m) où l et m sont les tailles des tableaux donnés en entrée. Comme on l'applique ici avec deux tableaux de taille n/2, sa complexité va être un O(n). On a donc un coût de la forme : C(n) = a + bn + 2C(n/2) avec a et b des constantes pour n>1, et C(1) = a. Comptons maintenant le nombre d'étapes : comme la taille est divisée par deux à chaque fois, on cherche le nombre k tel que n/(2^k)=1. Comme dans le cas de la dichotomie, ce nombre vaut floor(log(n)), après on tombe sur le cas de base n=1.

Développons un peu la complexité obtenue : C(n) = a + bn + 2C(n/2) = a + bn + 2(a + b*(n/2) + 2 * C(n/4)) = a + 2a + bn + bn + 4C(n/4). Comme ceci se répète floor(log(n)) fois avant de tomber sur le cas de base, on obtient un coût C(n) = a2^(floor(log(n))+1) + bnfloor(log(n)). En effet, la somme des 2^i * a pour i allant de 0 à floor(log(n)) vaut a * 2^(floor(log(n)) + 1).

En majorant floor(log(n)) par log(n), on obtient `C(n) array[b]){ //On échange les éléments extrêmes s'ils sont dans le mauvais sens var value = array[a]; array[a] = array[b]; array[b] = value; } if(b - a + 1 > 2){ // Si le tableau est de taille > 2, on trie par tiers var t = (b - a + 1)/3; stoogeSortBetween(array, a, ceil(b - t)); stoogeSortBetween(array, floor(a + t), b); stoogeSortBetween(array, a, ceil(b - t)); } }

function stoogeSort(@array){ stoogeSortBetween(array, 0, count(array) - 1); }

var array = [2, 5, 8, 3, 4, 7, 6, 1, 9, 11, 10, 17]; stoogeSort(array); debug(array); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 17]

Ce tri, s'il est simple à coder (et a le bon goût d'être en place, c'est-à-dire de ne pas consommer d'espace mémoire), est en fait assez inefficace. Pour le voir, comptons les appels récursifs. Puisque les opérations effectuées à chaque appel (un échange éventuel, et un test sur la longueur restant à trier) ne dépendent pas de la longueur du tableau, le nombre d'opérations sera directement un multiple de ce nombre d'appels. Je noterai donc C(n) ce nombre.

On a la formule de récurrence suivante, puisque la fonction se rappelle trois fois sur une longueur de 2/3 de la longueur initiale : C(n) = 3 * C(2n/3). Il faut donc trouver, pour savoir combien de fois on devra multiplier par 3, le nombre k tel que (2/3)^k * n = 2, et l'on aura alors C(n) = 3^k * C(2) (et C(2) est juste le nombre d'opérations pour échanger deux éléments).

Cela nous donne n/2 = (3/2)^k, d'où log(n/2) = k * log(3/2), soit k = log(n/2)/log(1.5). On obtient donc C(n) = 3^(log(n/2)/log(1.5)) * C(2), ce qui donne, après une petite manipulation de logarithmes et d'exponentielles, C(n) = (n/2)^(log(3)/log(1.5)) * C(2), d'où C(n) = O(n^(log(3)/log(1.5))) ≈ O(n^2.71).

Le code a donc une complexité polynomiale, mais plus grande que la complexité d'un tri simple (le tri par insertion par exemple, qui est en O(n^2)). En résumé, ce tri, en plus d'être intuitivement plus compliqué, est aussi plus lent que les tris simples. Il est donc, on peut le dire, tout pourri !

Exercice : le lecteur curieux pourra se demander ce qu'il se passe si l'on essaie de trier par ''quarts'', en triant des groupes de deux quarts à chaque fois (tout comme on triait des groupes de deux tiers ci-dessus). Et on peut aller plus loin : en cinquièmes, etc. Notamment, on remarquera que si on coupe en k morceaux avec k>3, il faut trier plus de k fois, ce qui fait qu'on perd sur le nombre de tris par étape, mais qu'on gagne sur la réduction de taille des tableaux à chaque étape. Quel tri classique retrouve-t-on si on pousse jusqu'à k = count(array)/2 ?

Récurrences d'ordre 2 : C(n)=f(C(n-1) , C(n-2)

Malheureusement, le monde n'est pas toujours si joli qu'au-dessus, et on peut parfois avoir des récurrences plus compliquées. La suite de Fibonacci en est un exemple classique : le tutoriel sur la récursivité vous a expliqué une méthode pour réduire la complexité obtenue avec la méthode naïve que je présente ci-dessous, mais ce cas de figure peut arriver dans d'autres algos, je vais donc traiter cet exemple.

Fibonacci

La suite de Fibonacci est une suite définie mathématiquement par u(0)=1, u(1)=1 et u(n) = u(n-1) + u(n-2) pour n>1. Traduit en code, cela donne :

function fibonacci(n){ if(n 1, avec pour arguments n-1 et n-2, on a C(n) = 2 + C(n-1) + C(n-2) (les appels à fibonacci(n-1) et fibonacci(n-2), plus les appels récursifs que ces deux appels vont provoquer). De plus, si n vaut 0 ou 1, il n'y a pas d'appels récursifs, donc C(0) = 0 et C(1) = 0. Remarquons que la relation de récurrence peut se récrire C(n) + 2 = (C(n-1) + 2) + (C(n-2) + 2). On pose donc u(n) = C(n) + 2, ce qui conduit à l'étude de la suite définie par :

u(0) = 2, u(1) = 2, et u(n) = u(n-1) + u(n-2) si n>1

On peut remarquer que cette suite est le double de celle de Fibonacci : la suite de Fibonacci donne quasiment son propre coût.

Bon, reste à étudier ce truc. Pour ça, je vous balance un théorème, et j'invite qui veut à me demander des explications sur le chat du jeu :

"Théorème : Soit u(n) une suite dans ℝ vérifiant, pour n > 1, u(n) = au(n-1) + bu(n-2). Si a²+4b > 0, alors il existe c et d dans ℝ tels que u(n) = c(x_1)^n + d(x_2)^n où x_1 et x_2 sont les racines de X²-aX-b. Si a²+4b = 0, alors il existe c et d dans ℝ tels que u(n) = (c + dn)(x_1)^n où x_1 est l'unique racine de X²-aX-b."

Dans le cas qui nous intéresse, on a a = 1 et b = 1. Les racines de X² - X - 1 sont données par x_1 = (1+sqrt(5))/2 (ce qu'on appelle le nombre d'or) et x_2 = (1-sqrt(5))/2. Ainsi, le théorème nous dit qu'il existe c et d tels que u(n) = c ((1+sqrt(5))/2)^n + d ((1-sqrt(5))/2)^n. Calculons c et d grâce aux valeurs de u(0) et de u(1) :

2 = u(0) = c ((1+sqrt(5))/2)^0 + d ((1-sqrt(5))/2)^0 = c + d

2 = u(1) = c ((1+sqrt(5))/2) + d ((1-sqrt(5))/2)

On en déduit, après un peu de manipulation de ces équations :

c = 1 + 1/sqrt(5) et d = 1 - 1/sqrt(5)

Ainsi, on a u(n) = (1 + 1/sqrt(5)) * ((1+sqrt(5))/2)^n + (1 - 1/sqrt(5)) * ((1-sqrt(5))/2)^n), et donc finalement :

C(n) = (1 + 1/sqrt(5)) * ((1+sqrt(5))/2)^n + (1 - 1/sqrt(5)) * ((1-sqrt(5))/2)^n) - 2.

Bon, c'est assez moche comme formule parce que j'ai détaillé les calculs, mais ce qui est important à voir là-dedans suit. On aurait tout à fait pu se passer de calculer les constantes pour l'analyse de la complexité !

Voici ce qui reste à noter : ((1-sqrt(5))/2)^n tend vers 0 quand n tend vers l'infini (car 0 ((1+sqrt(5))/2)^n tend vers l'infini quand n tend vers l'infini (car 1 fibonacci est O(((1+sqrt(5))/2)^n) : écrit comme ça, l'algorithme a une complexité exponentielle, alors que le tutoriel sur la récursivité propose un algorithme en temps linéaire. '''Il est donc important''', quand vous avez affaire à ce genre de récurrence, de regarder si une technique de mémoïsation ou de récursivité terminale ne pourrait pas s'appliquer !

On peut au passage remarquer qu'on a fait mieux que ça dans ce cas précis (et bim, remballe ta mémoïsation, Pump) : on a donné un algorithme en temps constant pour calculer la valeur de la fonction (avec une erreur d'arrondi due au passage par des flottants, certes, mais rien qu'un round ne puisse corriger) !

function fibonacci(n){ return (1 + 1/sqrt(5))/2 * ((1+sqrt(5))/2)n + (1 - 1/sqrt(5))/2 * ((1-sqrt(5))/2)n; }

Séries formelles

Là, on attaque vraiment les maths. Fuyez, pauvres fous !

Je vais maintenant présenter, grâce à un exemple, une technique de combinatoire assez puissante pour étudier des relations de récurrence plus compliquées.

Chemins de Dyck

Supposons que vous ayez une carte ressemblant à celle-ci, avec un écart de n cases horizontalement entre les cases bleues et rouges (ce qui fait un chemin de longueur 2n pour notre poireau) :

!Dyck_grid

et que, pour une raison mystérieuse, vous vouliez trouver tous les chemins menant de la case bleue à la case rouge n'allant jamais à contre-sens, c'est-à-dire ne retournant jamais vers la gauche (ce que l'on nomme chemins de Dyck). On a donc deux mouvements possibles à chaque étape : aller en bas à droite, ou aller en haut à droite.

Pour ça, écrivons un algo récursif, qui prend en entrée le nombre de mouvements vers le bas et vers le haut autorisés (sachant que, partant de tout en haut, on ne peut monter que si l'on est descendu avant) :

function getDyckPaths(n){ return getDyckPathsAux(0,n); }

getDyckPaths(3); // Donne down, down, down, up, up, up], [down, down, up, down, up, up], [down, down, up, up, down, up], [down, up, down, down, up, up], [down, up, down, up, down, up getDyckPaths(17); // Donne les chemins allant de la case bleue à la case rouge (enfin, ça donnerait ça si ça ne dépassait pas violemment les 20 millions d'opérations)

La complexité de cette fonction est difficile à évaluer : on a certes deux choix en général (aller en bas à droite ou aller en haut à droite), donc on pourrait penser à une complexité exponentielle, mais en réalité les mouvements sont forcés dès que l'on arrive sur une case verte :

!Dick_grid_forced_moves

Quand on est sur une case vert clair, on ne peut que monter, et sur une case vert foncé on ne peut que descendre.

Nous allons donc compter le nombre de chemins possibles pour étudier la complexité. Notons N(n) le nombre de chemins renvoyé par getDyckPaths(n), c'est-à-dire le nombre de chemins allant toujours vers la droite entre deux cases sur la même ligne séparés de n cases.

Si n = 0, il n'y a qu'un chemin : le chemin vide (celui qui reste sur place). Sinon, pour chaque chemin, on a deux cas possibles : soit il repasse sur la ligne entre l'arrivée et le départ (avant d'atteindre l'arrivée), soit il n'y repasse pas.

S'il n'y repasse pas, regardons la ligne juste sous celle reliant les cases de départ et d'arrivée : le chemin va commencer par descendre, ne va ensuite jamais repasser au-dessus de cette seconde ligne (car sinon il reviendrait sur la première ligne), et finir par monter.

!Dick_grid_case1

Dans ce cas, on s'est donc ramené à compter les chemins de Dyck entre les cases bleu clair et rose : on a N(n-1) possibilités.

S'il repasse sur la première ligne, il le fera potentiellement plusieurs fois. Soit k le plus grand entier tel que le chemin atteint la première ligne après 2k pas (il faut monter et descendre autant de fois pour retourner au même niveau, d'où la forme 2k). On peut donc scinder le chemin en deux chemins de Dyck plus petits :

!Dick_grid_case2

Si on impose de passer par la case violette, on se retrouve avec deux chemins de Dyck, celui allant de la case bleue à la case violette et celui allant de la case violette à la case rouge. On a donc N(k) possibilités pour le premier chemin, et N(n-k-1) pour le second (en effet, on a pris k le plus grand possible : entre les cases violette et rouge, le chemin ne repasse pas sur la première ligne, donc on est ramené au cas précédent), donc N(k)*N(n-k-1) en tout.

On peut donc écrire : N(n) = N(n-1) + somme(N(k)N(n-k-1), k=1..n-1), ce qui donne la formule de récurrence N(n) = somme(N(k)N(n-k-1), k=0..n-1).

Et là... On a l'air embêté. Cette formule de récurrence n'a pas l'air pratique du tout à première vue, elle fait intervenir une grosse somme et des produits. Et c'est là que les maths arrivent !

On va s'intéresser à la série (formelle, je ne ferai pas d'étude de convergence) suivante : S(X) = somme(N(n) X^n, n=0..infinity). On a alors :

!Dyck_calculs_1

On y reconnaît (si on a l'habitude, certes) un produit de convolution, on obtient donc :

!Dyck_calculs_2

Ainsi, on est ramené à exprimer S en fonction de X grâce à cette relation. Pour cela, on remarque que S(X) vérifie une équation d'ordre 2, de discriminant 1-4X. On pose ainsi S(X)= (1-sqrt(1-4X))/2X (on pourrait montrer que l'autre solution ne convient pas : le terme dominant en serait 1/X, ce qui fait tout foirer).

Comment obtenir les valeurs de N(n) à partir de ça ? Eh bien, grâce à un outil fabuleux : le développement en série (entière). Ici, on a :

!Dyck_calculs_3

Or, dans ce développement, par définition, les coefficients sont les N(i). On obtient donc la fabuleuse formule suivante : N(n) = (2n)!/((n+1)!n!). Ces nombres sont ce qu'on appelle les ''nombres de Catalan''.

On en déduit directement la complexité : pour chaque chemin trouvé, on a dû le créer en ajoutant autant d'éléments que la longueur du chemin, soit 2n. Ainsi, la complexité va être de O(2n * (2n)!/((n+1)!n!) = O(4^n / sqrt(n)) (et je vous épargne les calculs de l'équivalence entre ces deux O, ça découle de la formule de Stirling pour ceux qui voudraient savoir). Par rapport à la complexité exponentielle que l'on pouvait supposer au départ, on a donc gagné un facteur sqrt(n). Ce n'est pas grand chose, mais c'est toujours ça.

Contrairement à ce qu'on pourrait croire avec juste cet exemple, la difficulté est rarement dans la partie "développement en série". Ce qui est compliqué est généralement d'obtenir une équation fonctionnelle ou différentielle à partir de la formule de récurrence, puis de la résoudre. Cet outil est assez puissant, mais demande parfois de fortes capacités en mathématiques !

Pfiou. Bon, vous avez eu un aperçu de ce qu'on peut rencontrer quand on étudie des complexités de façon un peu plus précise que "Pouf, pouf, ça a l'air quadratique".

On peut donc passer aux complexités que vous ne rencontrerez pas !

Cas monstrueux

Normalement, vous ne rencontrerez pas ces cas, ce n'est pas pour autant qu'ils n'existent pas ! Cette section est juste là pour montrer que des fois, la complexité peut être énorme, elle n'est en quelque sorte là que pour le principe : si vous avez un algo qui a une complexité de ce genre, vous n'arriverez certainement pas à le faire tourner à part pour des entrées de très petite taille.

Fonction d'Ackermann

Cette fonction a été créée par Ackermann (d'où son nom) principalement pour des raisons théoriques : c'est historiquement un des premiers exemples de fonction non récursive primitive (avec la fonction de Sudan).

function Ackermann(m,n){ if(m === 0) return n + 1; if(n === 0) return Ackermann(m - 1, 1); return Ackermann(m - 1, Ackermann(m, n - 1)); }

Bon, ce que calcule cette fonction est loin d'être évident. Ce n'est même pas évident de voir pourquoi elle va forcément s'arrêter. En fait, on peut montrer qu'elle s'arrête en introduisant un ''ordre lexicographique'' sur les paires d'entiers : on dit que (a,b)Ackermann(m, n - 1) est bien un appel avec une paire plus petite car n-1Ackermann(m - 1, Ackermann(m, n - 1)) est un appel sur une paire plus petite car `m-1Ackermann(4,n) = 2^(2^(...)) - 3 avec n itérations de la puissance : la fonction, avec un m donné, va répéter n fois l'opération qu'elle faisait avec m-1.

Que dire alors de la complexité de la fonction suivante ?

function A(n){ return Ackermann(n,n); }

Remarquez déjà que la seule opération que fasse la fonction sur ce qu'elle renvoie est l'addition de 1, dans le cas où m vaut 0. Par exemple, pour A(2), la suite de calculs va ressembler à ça :

Ackermann(2,2) = Ackermann(1, Ackermann(2,1)) = Ackermann(1, Ackermann(1, Ackermann(2,0))) // Cas n = 0 = Ackermann(1, Ackermann(1, Ackermann(1,1))) = Ackermann(1, Ackermann(1, Ackermann(0, Ackermann(1, 0)))) // Cas n = 0 = Ackermann(1, Ackermann(1, Ackermann(0, Ackermann(0, 1)))) // Cas m = 0 = Ackermann(1, Ackermann(1, Ackermann(0, 2))) // Ackermann(0,1) vaut 2, on remplace : on a fait une addition. = Ackermann(1, Ackermann(1, 3)) //Ackermann(0,2) vaut 3, on remplace : une deuxième addition. = Ackermann(1, Ackermann(0, Ackermann(1,2))) = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(1,1)))) = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(0, Ackermann(1,0))))) // Cas n = 0 = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(0, Ackermann(0,1))))) // Cas m = 0 = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(0, 2)))) // Ackermann(0,1) vaut 2, on remplace : troisième addition. = Ackermann(1, Ackermann(0, Ackermann(0, 3))) // Ackermann(0,2) vaut 3, on remplace : quatrième addition. = Ackermann(1, Ackermann(0, 4)) // Ackermann(0,3) vaut 4, on remplace : cinquième addition. = Ackermann(1, 5) // Ackermann(0,4) vaut 5, on remplace : sixième addition. = Ackermann(0, Ackermann(1,4)) = Ackermann(0, Ackermann(0, Ackermann(1,3))) = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(1,2)))) = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(1,1))))) = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(0, Ackermann(1,0)))))) // Cas n = 0 = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(0, Ackermann(0,1)))))) //Cas m = 0 : on va pouvoir faire nos additions ! = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(0, 2))))) // Septième addition = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, 3)))) // Huitième addition = Ackermann(0, Ackermann(0, Ackermann(0,4))) // Neuvième addition = Ackermann(0, Ackermann(0, 5)) // Dixième addition = Ackermann(0, 6) // Onzième addition = 7 // Douzième addition et fin du calcul.

On a donc une trentaine de lignes de calcul, et une douzaine d'additions pour calculer A(2). Comme le résultat final est donné uniquement par des ajouts de 1, la complexité de A(n) va être supérieure à A(n) lui-même, ce qui ne peut même pas s'exprimer avec les opérations classiques ! On ne peut donc pas donner de complexité "simple".

En pratique, ben... A(2) se calcule bien, je l'ai même fait ici, avec en tout 27 appels récursifs et 12 additions. A(3) vaut 61, et son calcul demande 2432 appels récursifs. A(4) vaut 2^(2^65536))-3 et provoque un plantage de poireau si on essaie de le calculer. Ça croît donc très, très vite !

Suite de Syracuse

La suite de Syracuse associée à un entier de départ est une suite mathématique définie par :

u(0) = un entier positif n u(i) = u(i-1)/2 si u(i-1) est pair 3*u(i-1) + 1 sinon

Remarquez que si la suite prend à un moment la valeur 1, alors elle va ensuite prendre les mêmes valeurs périodiquement : de 1, on passe à 4, puis à 2, puis à 1, et on recommence.

On peut donc facilement coder une fonction qui prend en entrée l'entier de départ et qui calcule la suite de Syracuse associée jusqu'à tomber sur 1 :

function syracuse(n){ if(n === 1) {return "Fin du calcul";} if(n%2 === 0) { return syracuse(n/2); } else { return syracuse(3*n + 1); } }

Cette fonction va-t-elle s'arrêter quelque soit l'entrée ? Eh bien... Je ne sais pas. En fait, personne ne sait : la terminaison de cette fonction est un problème ouvert ! Il est donc impossible à l'heure actuelle de donner la complexité d'une telle fonction. Il faut donc faire attention : ce n'est pas parce qu'une fonction récursive a l'air simple que sa complexité est facile à étudier...