Complexité, récursivité

On considère l'algorithme suivant:

Sachant que Algo1(n) s'effectue en temps O(log n), Algo2(n) en temps O(n) et Algo3(n) en temps O(n²), quelle est la complexité de Algo(n)?

Quelle est la complexité de l'algorithme suivant?

Quelle est la complexité de l'algorithme suivant?

On veut calculer la suite de Fibonacci définie par u₀=u₁=1 et, pour tout n>=2 , u_n= u_n-1+u_n-2

Proposez un algorithme récursif simple pour calculer u_n . Estimez, sans detailler, sa complexité. Montrez les différents appels récursifs lors du calcul de u₄ . Comment améliorer l'algorithme?

Proposez une version itérative (non récursive) qui calcule u_n en temps linéaire.

Le problème des tours de Hanoï est originaire d'Inde où une légende raconte que, dans un temple où se trouvent trois poteaux sur lesquels s'empilent 64 disques d'or de diamètres différents, les prêtres de Brahmâ déplacent continuellement les disques d'un poteau de " départ " à un poteau d'" arrivée " en passant par un poteau " intermédiaire " selon les règles suivantes :

• on ne peut déplacer plus d'un disque à la fois,
• on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

On suppose que cette dernière règle est également respectée dans la configuration de départ. D'après cette même légende, le dernier déplacement de disque marquera la fin du monde.