Scribd
Importer
871 vues3 pages

Exercices sur la complexité algorithmique

Ce document contient 9 exercices de calcul de complexité d'algorithmes. Les exercices proposent différents algorithmes et fonctions récursives et demandent de calculer leur complexité en fonction des paramètres d'entrée comme la taille n d'une liste ou d'un tableau.

Transféré par

AssoumatiAzeddine
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
871 vues3 pages

Exercices sur la complexité algorithmique

Ce document contient 9 exercices de calcul de complexité d'algorithmes. Les exercices proposent différents algorithmes et fonctions récursives et demandent de calculer leur complexité en fonction des paramètres d'entrée comme la taille n d'une liste ou d'un tableau.

Transféré par

AssoumatiAzeddine
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Universit Mohamed Khider-Biskra

Dpartement dinformatique
2eme anne LMD
Srie dexercices N2

TD Algorithmique
Octobre 2011

Complexit des algorithmes


Exercice 1 Calculer la complexit de lalgorithme suivant :

Pour i de 2 n faire
k i-1 ;
x T[i] ;
Tant que (T[k] > x et k > 0) faire
T[k+1] T[k] ;
k k-1 ;
Fin TQ;
T[k+1] x ;
Fin Pour;

Exercice 2 Calculer la complexit de lalgorithme suivant :


i n;
S 0;
Tant que (i > 0) faire
j 2*i ;
Tant que (j > 1) faire
S S+(j-i)* (S+1) ;
j j-1 ;
Fin TQ;
i i div 2 ;
Fin TQ;

Exercice 3 Calculer la complexit de lalgorithme suivant :


i 1;
j 0;
Pour k de 1 n faire
j i+j ;
i j-i ;
Fin Pour;

Que fait cet algorithme sachant que le rsultat est dans j ?


Exercice 4 Calculer la complexit de la fonction rcursive suivante :
Fonction Fib( n : entier) : entier;
Dbut
Si (n < 2) Alors
Fib 1 ;
Sinon
Fib Fib(n - 1)+Fib(n - 2) ;
Fin Si;
Fin;

Exercice 5 Calculer la complexit de lalgorithme suivant :


P 1;
Pour I de 1 n faire
J 1;
K 1;
Tant que (K n) faire
P P * (K + J) ;
K K + 1;
Si (K > n) Alors
J J + 1;
Si (J > n) Alors
K1
Fin Si;
Fin Si;
Fin TQ;
Fin Pour;

Exercice 6 Calculer la complexit de lalgorithme suivant :


i 1;
Tant que (i < n) faire
j 1;
Tant que (j < 2*n) faire
j j*2 ;
Fin TQ;
i i+1 ;
Fin TQ;

Exercice 7 Trouver la complexit de la fonction suivante :

Var x : entier ;
Fonction f( i, j, k : entier) : entier;
Dbut
Si (k+j = i) Alors
f ((i-j) div k) + 1 ;
Sinon
x f(i, j+1, k-2) ;
f f(i+1, j+x, k-2) ;
Fin Si;
Fin;

Exercice 8 Trouver la complexit de lalgorithme suivant :

i 1;
j 1;
Tant que (i < n) faire
Si (j < n) Alors
j j * 2;
Sinon
j 1;
Fin Si;
i i + 1;
Fin TQ;

Exercice 9 Calculer la complexit de la procdure rcursive F(x, y, z) suivante :

Procdure F( x, y, z : reel);
Dbut
y 2*z ;
Si (x > x/(y - z)) Alors
x x - 2;
y y / 4;
z z / 5;
F(x, y, z) ;
Fin Si;
Fin;

*** Bonne chance ***


3

Vous aimerez peut-être aussi