Exercice n° :01

Soit deux algorithmes A1 et A2 avec leurs  temps d’exécution ( nombres d’opérations)  T1(n) = 3n²/5 et T2(n) = 26n + 12 respectives.

     1-Déterminer la complexité des deux algorithmes.  Quel algorithme a la meilleure complexité ?

     2-Quelle est la complexité de l’algorithme suivant ?

Algorithme compl ;

Début

       Si C1 alors  A1                                        { C1 est une condition simple de complexité O(1) }

                sinon  A2 ;

       Fin.

Exercice n° :02

On considère les algorithmes suivants avec la fonction T(n) qui représente le nombre des opérations

A1 : T(n) = 3n + 2

A2 : T(n) = 3

 

A3 : T(n) = 4n² + n + 2

A4 : Pour i ← 1 à n faire  A3 ;

        A1 ;

 

A5 :

Si c1 alors  A1

         Sinon  A2 ;

 A3 ;

C1 est une condition, Tc(n)=1

A6 : Pour i ← 1 `a 10 faire A1 ;

 

 -Déterminer la complexité des algorithmes de A1-A6

Exercice n° :03

Soit  l’algorithme suivant :

Algorithme exemple1 ;

Var   i,j,n s : entier ;

Debut

lire(n) ; s¬0 ;

pour i¬ n+2 à n+3  faire

     Pour j¬ 1 a n faire  s¬s+1 ;

écrire (s) ;

Fin.

1-      Déterminer la fonction de temps.

2-      Calculer la complexité de l’algorithme .

Exercice n° :04

Soit  l’algorithme suivant :

Algorithm exemple2 ;

Var   i,j,n s : entier ;

Debut

s¬0 ;lire(n) ;

pour i¬1 a n-1 faire

     Pour j¬ i+1 a n faire  s¬s+1 ;

ecrire (s) ;

Fin.

1-      Déterminer la fonction de temps.

2-      Calculer la complexité de l’algorithme .

Exercice n° :05

-Ecrire un algorithme qui calcule le produit de deux matrices carrées A(N,N) et B(N,N).

-Déterminer la fonction de temps

-Calculer la complexité de l’algorithme pour des matrices de taille N.

 Exercice n° : 06

 -Réécrire l’algorithme permettant de rechercher une valeur dans un  tableau trié par le principe de dichotomie

-Calculer la complexité de cet algorithme pour un tableau trié  de taille N.

Exercice n° : 07

Calculer la complexité de cet algorithme :

Algorithme inconnu ;

Var J,K,n :entier ;

DEBUT

  K¬1 ;

  Tantque(K<n) faire

debut

  J¬1 ;

  Ttantque(J < K) faire

                             debut

                               écrire(‘si tu veux , tu peux ‘) ;

                               J¬J*2 ;

                                fintq 

  K ¬K+1 ;

fintq 

FIN .

Last modified: Sunday, 22 October 2023, 9:13 PM