/

Analyse des Algorithmes

Dr. Taggar Hamza

Dans ce chapitre, nous allons focaliser notre attention à l’analyse des algorithmes, l’objectif de cette analyse est de :

  •  – Prévoir le temps nécessaire pour l’exécution d'un algorithme.
  •  – Pouvoir comparer plusieurs algorithmes réalisant le même traitement.

Analyse des algorithmes

Lorsque nous voulons proposer un algorithme pour résoudre un problème particulier, nous de- vons d'abord le faire fonctionner correctement, puis réfléchir à bien le faire, et enfin nous pen- sons à l'amener à résoudre ce problème le plus rapidement possible.

Qualités d’un bon algorithme

Souvent, les algorithmes sont proposés pour être traduit sous forme des programmes pour qu’ils puissent être exécutés par des ordinateurs. A partir de là, nous commençons à penser à l’analyse de la qualité des algorithmes proposés. Pour obtenir un bon programme, il faut partir d’un bon algorithme qui doit posséder, entre autres, les qualités suivantes:

  • Lisible : il doit être clair, bien commenté, et facile à comprendre par tous ceux qui le lisent
  • Correcte : il faut que l’algorithme propose correctement des solutions aux problèmes pour lesquels il a été conçu.
  • Lisible : il doit être clair, bien commenté, et facile à comprendre par tous ceux qui le lisent
  • Complet : il doit être le plus général possible pour répondre à toutes les spécifications en apportant des solutions à tout cas possible
  • Efficace : L’algorithme doit être conçu de manière à limiter le nombre d’opérations élé- mentaires à effectuer et doit aussi minimiser l’utilisation de l’espace mémoire.

Exemples de calcul de la valeur d’un polynôme

Nous étudierons 3 variantes d’algorithmes pour calculer la valeur d’un polynôme. Soit 𝑃ሺ𝑥ሻ un polynôme de degré 𝑛, tel que 𝑃(x)= a nX𝑛 + a n-1X𝑛-1+ ... +a1X + a0 ou 𝑛 et entier naturel et a n, a n-1..., a 1, a 0 sont les coefficients du polynôme. Nous définirons cette structure comme suit : 

struct polynome{
int degre;
float coef[tailleMax];
};

typedef struct polynome var_polynome;

Pour calculer la valeur de polynôme, nous définissons la procédure Lire_polynome() qui lit le degré et les valeurs des coefficients d’un polynôme ; et une autre fonction puissances() qui calcule le terme 𝑋n . 

void Lire_polynome(var_polynome *p){
    
    int i;

    printf("entrez le degre de polynome:");

    scanf("%d", &(*p).degre);

    for(i=(*p).degre ; i>=0 ; i-- ){
        printf("entrez le coefficient a%d:", i);
        scanf("%f" ,&(*p).coef[i]); 
    }

}

int puissance(int x, int y){

    int p = 1;
    if ( y == 0 ) return 1;
    else
        while( y > 0){
            p=p*x;
            y--;
        }
    return p;
}

Exemple 1

/* Variante 1: fonction qui prend en entrée deux paramètres:
- Une variable de type structure
- la valeur d'un réel x
la fonction calcule et renvoie la valeur d'un polynôme
en utilisant la fonction puissance */

float valeur_polynome_variante1(var_polynome p, float x){

    float s = 0.0;
    int i;
    for( i = 0; i<=p.degre ; i++) {
        s=s+(p.coef[i]*puissance(x,i));
    }

    return s; 
}
coût de la première variante: Nous allons calculer les coûts des algorithmes en comptant le nombre des opérations d’addition et de multiplication effectuées dans la boucle. Pour un polynôme de degré n , la première va- riante de cet algorithme effectue :
  • ( n + 1) additions
  • ( n + 1) multiplications
  • ( n + 1) appels à la fonction puissance(x, i)

Le coût de chaque appel est de 𝑖 opérations de multiplication. Le coût total des appels dans la boucle est

∑i=1n i = n+1⁄2(n+0) = n⁄2(n+1)

Donc le coût de la première variante est :

cout(V1) = (n+1)+(n+1)+ n⁄2(n+1)

Cout(V1) ( 2 + n⁄2 )(n+1)

Exemple 2

/* Variante 2: la valeur du polynôme est calculée sans utilisation de la fonction puissance */
    
    float valeur_polynome_variante2(var_polynome p, float x){
        int pow = 1;
        int i;
        float s = 0.0;
        for (i=0 ; i <=p.degre ;i++){
            s=s+(p.coef[i]*pow); 
            pow=pow*x;
        } 
        return s;
    }
Le coût de la deuxième variant :

Pour un polynôme de degré 𝑛 , la deuxième variante de cet algorithme effectue :

  • ( n + 1) additions
  • 2( n + 1) multiplications
Soit un total : 𝐶𝑜û𝑡(V2) = 3 (𝑛+1)

Exemple 3

/* Variante 2: la valeur du polynôme est calculée 
   sans utilisation de la fonction puissance  */ 

    float valeur_polynome_variante2(var_polynome p, float x){
        int pow = 1;
        int i;
        float s= 0.0;
        for (i=0 ;i<=p.degre;i++){
            s=s+(p.coef[i]*pow); 
            pow=pow*x;
        } 
        return s;
    }
Le coût de la troisième variante :

Pour un polynôme de degré 𝑛 , la deuxième variante de cet algorithme effectue :

  • 𝑛 additions
  • 𝑛 multiplications

𝐶𝑜û𝑡(V3) = 2𝑛

Table of contents