Récursion et Big O

Question

J'ai travaillé récemment sur un devoir d'informatique impliquant la récursivité et la notation big-O. Je crois que je comprends assez bien (certainement pas parfaitement, cependant!) Mais il y a une question en particulier qui me pose le plus de problèmes. Ce qui est étrange, c’est qu’en le regardant, c’est le plus simple des devoirs.

Fournir le meilleur taux de croissance en utilisant la notation big-Oh pour résoudre le problème suivant?

T (1) = 2

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

Et les choix sont les suivants:

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

Je comprends que Big O fonctionne comme une limite supérieure, pour décrire le plus grand nombre de calculs, ou le temps d’exécution le plus long, que ce programme ou processus prendra. Je pense que cette récursion particulière devrait être O (n), car, tout au plus, elle 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), ou pire, étant les trois autres options.

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

Answer 1

Il existe différentes manières de résoudre les récurrences: substitution, arbre de récurrence et théorème principal. Le théorème principal ne fonctionnera pas dans ce cas car il ne correspond pas à la forme du théorème principal.

Vous pouvez utiliser les deux autres méthodes, mais le moyen le plus simple de résoudre ce problème consiste à le résoudre de manière itérative.

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

Voir le motif?

T (n) = 2 ^n-1 & # 8901; T (1) + 2 ^n-2 + 2 ^n-3 + ... + 1
T (n) = 2 ^n-1 & # 8901; 2 + 2 ^n-2 + 2 ^n-3 + ... + 1
T (n) = 2 ⁿ + 2 ^n-2 + 2 ^n-3 + ... + 1

Par conséquent, la limite la plus étroite est & # 920; (2 ⁿ ).

Answer 2

Je pense que vous avez un peu mal compris la question. Il ne vous demande pas combien de temps cela prendrait pour résoudre la récurrence. Il s'agit de demander quel est le big-O (le lien asymptotique) de la solution elle-même.

Ce que vous devez faire est de proposer une solution sous forme fermée, i. e. la formule non-récursive pour T (n), puis déterminez quel est le grand-O de cette expression.

Answer 3

La question est de demander la notation big-oh pour la solution à 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 séquence 2, 5, 11, 23, 47, ...

La bonne façon de résoudre ce problème consiste à résoudre les équations de récurrence.

Answer 4

Je pense que ce sera exponentiel. Chaque incrément à n rend la valeur deux fois plus grande.

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

T (x) correspond à la durée 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 5

  

Je pense que ce sera exponentiel. Chaque incrément à n apporte deux fois plus de calculs.

Non, ce n'est pas le cas. Bien au contraire:

Considérons que pour les n itérations, nous obtenons le temps d'exécution R . Ensuite, pour n + 1 itérations, nous aurons exactement R + 1.

Ainsi, le taux de croissance est constant et le temps d’exécution global est bien O ( n ).

Cependant, je pense que l'hypothèse de Dima sur la question est juste, bien que sa solution soit trop compliquée:

  

Ce que vous devez faire est de proposer une solution sous forme fermée, i. e. la formule non-récursive pour T (n), puis déterminez quel est le grand-O de cette expression.

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

Answer 6

Tout d’abord, les quatre réponses sont pires que O (n) ... O (n * log n) est plus complexe que l’ancien O (n). Quoi de plus grand: 8 ou 8 * 3, 16 ou 16 * 4, etc ...

Passons à la question actuelle. La solution générale peut évidemment être résolue en temps constant si vous ne faites pas de récursivité

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

Et comme vous pouvez le constater, 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).

Donc, cela semble être une question mal formulée, et ils vous demandent probablement la croissance de la fonction elle-même, pas la complexité du code. C'est 2 ^ n. Maintenant, va faire le reste de tes devoirs ... et étudie O (n * log n)

Answer 7

Calculer une solution de forme fermée à la récursivité est facile. En inspectant, vous devinez que la solution est

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

Ensuite, vous prouvez par induction que c'est effectivement 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 récurrence, et le second de l'hypothèse inductive. QED.

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

Aux personnes qui ont répondu à O (n): Je suis tout à fait d’accord avec Dima. Le problème ne pas demandé la borne supérieure la plus étroite à la complexité de calcul d'un algorithme de calcul de T (n) (qui serait maintenant O (1), puisque sa forme fermée a été fournie). Le problème demande la borne supérieure la plus stricte sur T (n) lui-même , et c’est la solution exponentielle.