Mesure du temps d'exécution / Complexité

Version imprimable

Bonjour,
Je suis prof de maths et j'enseigne depuis cette année le TurboPascal en prépa ECS1. Pour introduire le "calcul" de la complexité d'un algorithme, je souhaiterais faire mesurer les temps d'exécution de plusieurs algorithmes par les étudiants puis faire émerger le besoin d'estimer la complexité de chaque algorithme.
Pouvez-vous m'indiquer comment mesurer le temps d'exécution par exemple de l'algorithme suivant (calcul coef binomial par la formule de Pascal):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
program ex_28;                                                                
var n,k,i,j:integer; T:array[0..100,0..100] of integer;                       
begin                                                                         
writeln('saisir n et k');                                                     
readln(n,k);                                                                  
for i:=0 to n do                                                              
    begin                                                                     
    for j:=0 to i do                                                          
        begin                                                                 
             if (j=0) or (i=j) then T[i,j]:=1                                 
             else T[i,j]:=T[i-1,j]+T[i-1,j-1];                                
             {write(T[i,j]:4,' ');}                                           
        end;                                                                  
    writeln;                                                                  
    end;                                                                      
writeln(k,' parmi ',n,' vaut ',T[n,k]);                                       
readln;                                                                       
end.

Merci beaucoup par avance,
Emmanuel

pense à mettre la balise code pour la presentation du code.

Je vais tenter d'etudier le temps d'execution des boucles for imbriquées.
On suppose que le bloc if s'execute en un temps egal à O(1) c'est à dire un temps constant.
Pour une valeur de i donné, on effectue i+1 boucle (cette parametré avec j). Si on essaie de voir les valeur, on s'aperçoit qu'on a affaire à une suite arithmetique:

Citation:

u(0)=1
u(1)=2
...
u(n)=n+1

Le temps total pris par les boucle sera egal à la somme de cette suite arithmetique :

Citation:

s=(n+1)*(1+(n+1))/2

Nous pouvons alors dire que ce programme s'execute en O(n^2) si on neglige les terme en n et les facteurs constants.

J'ai mis un compteur dans le code que tu as posté pour donner le nombre de tour fait par la boucle
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 program ex_28; var n,k,i,j:integer; T:array[0..100,0..100] nbr : integer; begin writeln('saisir n '); readln(n); nbr:=0; for i:=0 to n do begin for j:=0 to i do begin if (j=0) or (i=j) then T[i,j]:=1 else T[i,j]:=T[i-1,j]+T[i- nbr:=nbr+1; end; end; writeln('nombre de tour :', nbr); readln; end.

19/02/2009, 20h36
egrand

Merci pour cette réponse.
C'est une bonne idée de mettre le compteur.
Est-il possible (pertinent?) de mesurer le temps d'exécution à la manière de scilab ou matlab avec un timer?
Merci d'avance,
Emmanuel
19/02/2009, 22h38
Gabi

1 pièce(s) jointe(s)

Salut,

tu peux utiliser la fonction Rdtsc. Et pour simplifier les choses, utiliser l'unité de HDD34, "Timer", en fichier joint.

Pour plus d'infos sur le Rdtsc, lis la page de Haypo ici:
http://haypo.developpez.com/article/frequence_cpu/.

Je me suis permis d'ajouter une unité que j'ai faite ("Uchronos") à partir de "Timer". Elle a l'avantage d'être plus simple à prendre en main (pour moi en tout cas;)). Par contre, pour la faire marcher, il faut indiquer dans l'unité la fréquence du processeur (constante "Fproc"). Je pense que ça marchera, même si j'ai pas pensé qu'un jour le le passerai à quelqu'un.

Le principe est simple: créer un chrono ou utiliser le tableau "chronos". Puis il y a "TopDepart" à mettre dans le programme quand on veut le faire démarrer (du style

Code:

chronos[1].TopDepart;

), TopInt (intermédiaire) pour mesurer un temps sans arrêter le chrono. Et "TopFin" pour arrêter le chrono, il suffit alors d'appeler la fonction "Dt" pour connaître l'intervalle de temps en milli secondes, avec 3 chiffres après la virgule. La précision est donc à la microseconde, mais il faut être sûr de la fréquence proc.

Bon j'ai assez parlé, je vais me coucher, bonne nuit à tous :zzz:
20/02/2009, 10h10
Prof

Bonjour.

Le plus simple, pour des élèves qui ne sont pas familiarisés avec la programmation, c'est d'utiliser la fonction GetTime de TurboPascal.

Cette fonction fait partie de l'unité Dos et sa syntaxe est :
GetTime( var heure, minute, seconde, sec100 : word );

( voir l'aide en ligne de TurboPascal )

Il suffit d'appeler cette fonction avant une boucle avec un premier jeu de variables, puis de l'appeler une seconde fois après la boucle avec un deuxième jeu de variables.
La différence entre les deux jeux de variables fournira le temps écoulé, en centième de seconde.
20/02/2009, 11h24
Gabi

C'est vrai que c'est encore plus simple (Je l'avais déjà oubliée cette fonction :oops:).
Et dans le cas où le temps d'exécution est inférieur à la résolution de GetTime, il suffit de mesurer le temps après 100 opérations pour avoir une estimation du temps d'une opération au dixième de ms!
21/02/2009, 12h17
egrand

Merci à tous pour vos réponses utiles.
J'utiliserai avec mes prépa la solution de Prof avec GetTime et l'unité Dos. C'est ce que j'ai trouvé de plus simple pour eux (et pour moi aussi d'ailleurs!!).
A bientôt,
Emmanuel