Récursion et Big O

Question

J'ai travaillé sur un récent devoir d'informatique impliquant une récursion et la notation big-O. Je crois que je comprends assez bien (mais certainement pas parfaitement !) mais il y a une question en particulier qui me pose le plus de problèmes. Ce qui est étrange, c'est qu'en la regardant, elle semble être la plus simple du devoir.

Donnez le meilleur taux de croissance en utilisant la notation big-Oh pour la solution de la récurrence suivante ?

T(1) = 2

T(n) = 2T(n - 1) + 1 pour n>1

Et les choix sont :

• O(n log n)
• O(n^2)
• O(2^n)
• O(n^n)

Je comprends que le grand O fonctionne comme une limite supérieure, pour décrire le plus grand nombre de calculs, ou le temps d'exécution le plus élevé, qu'un programme ou un processus prendra. J'ai l'impression que cette récursion particulière devrait être O(n), puisque, au maximum, la récursion ne se produit qu'une fois pour chaque valeur de n. Puisque n n'est pas disponible, c'est soit mieux que cela, O(nlogn), soit pire, étant les trois autres options.

Donc, ma question est la suivante : pourquoi n'est-ce pas O(n) ?

Answer 1

Il existe plusieurs façons de résoudre les récurrences : substitution, arbre de récurrence et théorème central. Le théorème maître ne fonctionnera pas dans ce cas, car il ne correspond pas à la forme du théorème maître.

Vous pouvez utiliser les deux autres méthodes, mais le plus simple pour ce problème est de le résoudre par itération.

T(n) = 2T(n-1) + 1
T(n) = 4T(n-2) + 2 + 1
T(n) = 8T(n-3) + 4 + 2 + 1
T(n) = ...

Vous voyez le modèle ?

T(n) = 2 n-1 ⋅T(1) + 2 n-2 + 2 n-3 + ... + 1
T(n) = 2 n-1 ⋅2 + 2 n-2 + 2 n-3 + ... + 1
T(n) = 2 n + 2 n-2 + 2 n-3 + ... + 1

Par conséquent, la limite la plus étroite est Θ(2 n ).

Answer 2

Je pense que vous avez un peu mal compris la question. Elle ne vous demande pas combien de temps il faudrait pour résoudre la récurrence. Elle demande quel est le big-O (la limite asymptotique) de la solution elle-même.

Ce qu'il faut faire, c'est trouver une solution en forme fermée, c'est-à-dire la formule non récursive de T(n), et déterminer ensuite quel est le grand O de cette expression.

Answer 3

Je pense que cela va être exponentiel. Chaque incrément de n rend la valeur deux fois plus grande.

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

T(x) serait le temps d'exécution du programme suivant (par exemple) :

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)

Answer 4

La question demande la notation big-Oh pour la solution de la récurrence, pas le coût du calcul de la récurrence.

En d'autres termes : la récurrence produit :

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

Quelle notation big-Oh décrit le mieux la suite 2, 5, 11, 23, 47, ...

La façon correcte de résoudre cela est de résoudre les équations de récurrence.

Answer 5

Je pense que cela va être exponentiel. Chaque incrément à n apporte deux fois plus de calcul.

Non, ça ne l'est pas. Bien au contraire :

Considérons que pour n itérations, nous obtenons un temps de fonctionnement R . Alors pour n + 1 itérations, nous obtiendrons exactement R + 1.

Ainsi, le taux de croissance est constant et le temps de fonctionnement global est bien O ( n ).

Cependant, je pense que l'hypothèse de Dima concernant la question est correcte, même si sa solution est trop compliquée :

Ce qu'il faut faire, c'est trouver une solution en forme fermée, c'est-à-dire la formule non récursive de T(n), et ensuite déterminer quel est le grand O de cette expression.

Il suffit d'examiner la taille relative de T ( n ) et T ( n + 1) itérations et déterminer le taux de croissance relatif. La quantité double évidemment ce qui donne directement la croissance asymptotique.