Travail sur l'algorithmique.(TP et TD)

1)Ecrire une fonction itérative puis une autre récursive qui donne la valeur de factorielle n.
Calculer la complexité de chaque.
Faire une preuve de chaque.

Elèments de réponse:

Itératif:fact(n)
u=1
pour i allant de 1 à n 
   u=uxi
 retourner u
 
 Récursif:fact(n)
 si n=0 (ou n<=0) retourner 1(Un si est nécessaire en récursif pour que l'empilement des appels s'arrêtent)
 sinon retourner nxfact(n-1)
 
Pour la complexité dans le cas itératif elle vaut le nombre de boucles xnombre d'opérations dans chaque boucles.
et dans le cas récursif elle vérifie une relation de récurrence:Uo=0 et pour tout n Un=1+Un-1(suite arithmétique)
On trouve O(n) dans les 2 cas.
Pour la preuve on cherche un invariant de fin de boucle ou de fin d'appel qui se démontre par récurrence:
Dans le cas itératif "A la fin de la boucle i u contient i!"
Dans le cas récursif "A la fin de l'appel à fact(i) fact(i) retourne i!"

Une conséquence de cet invariant est fact(n) retourne n! (dernière boucle ou dernier appel) ce qui
démontre que fact(n) fait bien ce qu'elle doit faire.

2)Ecrire une fonction de recherche d'un entier dans un tableau d'entiers triés (récursive et dichotomique)
  Calculer la complexité.
  Pour la complexité , on remarquera que si n= 2 puissance k et si on note u(k)=C(n) (complexité pour un tableau
  de taille n) alors u(k-1)=C(n/2).
  
 3)Ecrire la fonction tri-insertion
   Complexité en O(n carré) 
   
 4)Ecrire la fonction tri-fusion
   Complexité en O(nlog(n))