^{PDFprof.com Search Engine}

Travaux Dirigés Algorithmique no3

Quel est l’algorithme du tri par insertion ?
Le nombres d’opérations élémentaires étant constant lors d’une itération de la bouclewhile, on peut conclure que dans le cas moyen, l’algorithme du tri par insertion est de complexitéΘ (n 2 ).
Comment calculer l’algorithme de Karatsuba ?
Remarque : l’algorithme de Karatsuba est enΘ (nlog 2 (3)), ornlog 2 (3)≃ 1. 59 donc il est plus efficace que l’algorithme de multiplication classique. ∑logb (n) i=0 (bac)i= Θ (1). ∑logb (n) i=0 (bac)i= Θ (logb (n)). logb (n)).
Comment montrer que l’algorithme bincount est enω ?
On peut le montrer par induction : Initialisation :C (0,0)retourne 1 etC 00 = 1. Supposons queC (n− 1 , p) retourne la valeurCpn− 1 ,∀p≤n− 1. L’algotri denest enΘ (n)si le plus grand élément du tableauA (m) est enΘ (n). L’algorithmebincount (n)fait au moinsn− 1 affectations dej= 0donc il est clairement enΩ (n).

Quel est l’algorithme du tri par insertion ?