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

Tout d'abord, les quatre réponses sont pires que O(n)... O(n*log n) est plus complexe que le bon vieux O(n). Qu'est-ce qui est plus grand : 8 ou 8 * 3, 16 ou 16 * 4, etc...

Venons-en à la vraie question. La solution générale peut évidemment être résolue en temps constant si vous ne faites pas de récursion.

( T(n) = 2^(n - 1) + 2^(n) - 1 ), donc ce n'est pas ce qu'ils demandent.

Et comme vous pouvez le voir, si nous écrivons le code récursif :

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

C'est évidemment O(n).

Il semble donc qu'il s'agisse d'une question mal formulée, et ils vous demandent probablement la croissance de la fonction elle-même, et non la complexité du code. C'est 2^n. Maintenant, allez faire le reste de vos devoirs... et étudiez O(n * log n).

Answer 2

Il est facile de calculer une solution sous forme fermée pour la récursion. Par inspection, vous devinez que la solution est

T(n) = 3\*2^(n-1) - 1

Ensuite, vous prouvez par induction qu'il s'agit bien d'une solution. Cas de base :

T(1) = 3\*2^0 - 1 = 3 - 1 = 2. OK.

Induction :

Suppose T(n) = 3\*2^(n-1) - 1. Then
T(n+1) = 2\*T(n) + 1 = 3\*2^n - 2 + 1 = 3\*2^((n+1)-1) - 1. OK.

où la première égalité découle de la définition de la récurrence, et la seconde de l'hypothèse inductive. QED.

3*2^(n-1) - 1 est clairement Thêta(2^n), donc la bonne réponse est la troisième.

Aux personnes qui ont répondu O(n) : Je ne pourrais pas être plus d'accord avec Dima. Le problème est no demander la limite supérieure la plus étroite de la complexité de calcul d'un algorithme pour calculer T(n) (qui serait maintenant O(1), puisque sa forme fermée a été fournie). Le problème demande la limite supérieure la plus stricte sur T(n) lui-même et c'est l'exponentielle.