Détermination de la complexité pour les fonctions récursives (notation Big O)

J’ai un cours d’informatique à mi-parcours demain et j’ai besoin d’aide pour déterminer la complexité de ces fonctions récursives. Je sais comment résoudre des cas simples, mais j’essaie toujours d’apprendre à résoudre ces cas plus difficiles. Ce ne sont là que quelques exemples de problèmes que je n’ai pu trouver. Toute aide serait très appréciée et aiderait grandement dans mes études, merci!

int recursiveFun1(int n) { if (n <= 0) return 1; else return 1 + recursiveFun1(n-1); } int recursiveFun2(int n) { if (n <= 0) return 1; else return 1 + recursiveFun2(n-5); } int recursiveFun3(int n) { if (n <= 0) return 1; else return 1 + recursiveFun3(n/5); } void recursiveFun4(int n, int m, int o) { if (n <= 0) { printf("%d, %d\n",m, o); } else { recursiveFun4(n-1, m+1, o); recursiveFun4(n-1, m, o+1); } } int recursiveFun5(int n) { for (i = 0; i < n; i += 2) { // do something } if (n <= 0) return 1; else return 1 + recursiveFun5(n-5); } 

La complexité temporelle, en notation Big O, pour chaque fonction, est en ordre numérique:

  1. La première fonction est appelée récursivement n fois avant d’atteindre le cas de base, donc son O(n) , souvent appelé linéaire .
  2. La deuxième fonction est appelée n-5 à chaque fois, nous déduisons donc cinq de n avant d’appeler la fonction, mais n-5 est aussi O(n) . (Actuellement appelé ordre de n / 5 fois. Et, O (n / 5) = O (n)).
  3. Cette fonction est log (n) base 5, car chaque fois que nous divisons par 5 avant d’appeler la fonction, son O(log(n)) (base 5), souvent appelé logarithmique et le plus souvent la notation Big O et la complexité utilise la base 2 .
  4. Dans le quasortingème, il s’agit de O(2^n) , ou exponentielle , puisque chaque appel de fonction s’appelle lui-même deux fois s’il n’a pas été récursif n fois.
  5. Comme pour la dernière fonction, la boucle for prend n / 2 puisque nous augmentons de 2, et la récursion prend n-5 et comme la boucle for est appelée récursivement, la complexité temporelle est dans (n-5) * (n / 2) = (2n-10) * n = 2n ^ 2- 10n, en raison du comportement asymptotique et des considérations du scénario le plus défavorable ou de la limite supérieure que recherche le grand O, le terme le plus grand nous intéresse seulement O(n^2) .

    Bonne chance sur vos midterms;)

Pour le cas où n <= 0 , T(n) = O(1) . Par conséquent, la complexité du temps dépendra du moment où n >= 0 .

Nous considérerons le cas n >= 0 dans la partie ci-dessous.

1.

 T(n) = a + T(n - 1) 

où a est une constante.

Par induction:

 T(n) = n * a + T(0) = n * a + b = O(n) 

où a, b sont des constantes.

2.

 T(n) = a + T(n - 5) 

où a est une constante

Par induction:

 T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n) 

où a, b sont des constantes et k <= 0

3.

 T(n) = a + T(n / 5) 

où a est une constante

Par induction:

 T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n) 

où a, b sont une constante

4.

 T(n) = a + 2 * T(n - 1) 

où a est une constante

Par induction:

 T(n) = a + 2a + 4a + ... + 2^n * a + T(0) * 2 ^ n = a * 2^(n+1) - a + b * 2 ^ n = (2 * a + b) * 2 ^ n - a = O(2 ^ n) 

où a, b sont des constantes.

5.

 T(n) = n / 2 + T(n - 5) 

On peut prouver par induction que T(5k) >= T(5k - d) où d = 0, 1, 2, 3, 4

Ecrire n = 5m - b (m, b sont des nombres entiers; b = 0, 1, 2, 3, 4), alors m = (n + b) / 5 :

 T(n) = T(5m - b) <= T(5m) 

(En fait, pour être plus rigoureux ici, une nouvelle fonction T'(n) devrait être définie telle que T'(5r - q) = T(5r)q = 0, 1, 2, 3, 4 . T(n) <= T'(n) comme prouvé ci-dessus. Quand on sait que T'(n) est dans O(f) , ce qui signifie qu'il existe une constante a, b pour que T'(n) <= a * f(n) + b , on peut déduire que T(n) <= a * f(n) + b et donc T(n) est dans O(f) . Cette étape n'est pas vraiment nécessaire, mais il est plus facile de penser quand vous n'avez pas à traiter avec le rest.)

T(5m) expansion T(5m) :

 T(5m) = 5m / 2 + T(5m - 5) = (5m / 2 + 5 / 2) * m / 2 + T(0) = O(m ^ 2) = O(n ^ 2) 

Par conséquent, T(n) est O(n ^ 2) .

L’une des meilleures façons de trouver une approximation de la complexité de l’algorithme récursif consiste à dessiner l’arbre de récurrence. Une fois que vous avez l’arbre récursif:

 Complexity = length of tree from root node to leaf node * number of leaf nodes 
  1. La première fonction aura la longueur de n et le nombre de nœuds feuilles 1 donc la complexité sera n*1 = n
  2. La seconde fonction aura à nouveau la longueur n/5 et le nombre de nœuds feuilles 1 donc la complexité sera n/5 * 1 = n/5 . Il faut l’approcher de n

  3. Pour la troisième fonction, puisque n est divisé par 5 à chaque appel récursif, la longueur de l’arbre récursif sera log(n)(base 5) et le nombre de nœuds feuilles à nouveau 1, donc la complexité sera log(n)(base 5) * 1 = log(n)(base 5)

  4. Pour la quasortingème fonction puisque chaque nœud aura deux nœuds enfants, le nombre de nœuds feuilles sera égal à (2^n) et la longueur de l’arbre récursif sera n , la complexité sera (2^n) * n . Mais comme n est insignifiant devant (2^n) , on peut l’ignorer et on peut seulement dire que la complexité est (2^n) .

  5. Pour la cinquième fonction, deux éléments introduisent la complexité. La complexité introduite par la nature récursive de la fonction et la complexité introduite par for loop dans chaque fonction. En faisant le calcul ci-dessus, la complexité introduite par la nature récursive de la fonction sera ~ n et la complexité due à la boucle n . La complexité totale sera n*n .

Note: Ceci est un moyen rapide et sale de calculer la complexité (rien d’officiel!). Aimerait entendre des commentaires à ce sujet. Merci.