Complexité Algorithmique

n), O(10 n) sur une courbe (taille des données en abscisse et temps d’exécution en ordonnée).

Donner l’allure des différentes courbes sur un même schéma.

2) Quel est le nombre le plus grand entre : 10 100 ou 100 10 ? Expliquer ça en utilisant les classes

de complexité.

3) Etant donné un ordinateur X qui permet de traiter 10 milliards d’opérations élémentaires par

seconde. supposant que les programmes P1 et P2 ont été lancés simultanément sur la

machine. Quel programme terminera le premier ? Quel est le temps nécessaire (en minutes

et en secondes) pour exécuter toute les instructions de P1 et P2 ?

P1

i=1 \\(1 opération élémentaire )

While (i<1018 ) \\(1 opérations

élémentaires)

{ i=i*2 } \\(2 opérations

P2

i=1 \\(1 opération élémentaire )

While (i<1018 ) \\(1 opération

élémentaire)

{ i=i+10 } \\(2 opérations

élémentaires)

élémentaires)

4) Quel est la complexité asymptotique de ce programme ? donner le détail de calcul

int i =1 ;int K=1;

While ( i<=n && k<=n ) {

int j=i ; int x=0;

While (j < k)

{ x=x+1; j++; }

i=i+2;

K=K*2

}

Problème (10 points)

On propose d’implémenter un algorithme qui sauvegarde les permutations possibles d’un ensemble

des n éléments distincts {1, 2, …, n} dans une matrice PERMUT de largeur n. Par exemple pour

l’ensemble (1, 3, 2) la matrice PERMUT est :

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

1) Quel est le nombre de permutations attendues ? quel serait alors la longueur de la matrice

PERMUT ?

2) Donner une idée d’implémentation de l’algorithme.

3) Donner le code d’implémentation (notation algorithmique ou un langage choisi)

4) Quel est la complexité du programme proposé.