Compléxité. [Résolu/Fermé]

Signaler
Messages postés
81
Date d'inscription
mercredi 4 mai 2005
Statut
Membre
Dernière intervention
14 septembre 2007
-
Messages postés
81
Date d'inscription
mercredi 4 mai 2005
Statut
Membre
Dernière intervention
14 septembre 2007
-
Bonjour à tous;
Est ce que c'est possible de savoir la compléxité de mon algorithme ou code C++?? nombre d'opérations ou temps de calcul??
Bonne journée.

5 réponses

Messages postés
248
Date d'inscription
lundi 26 juin 2006
Statut
Membre
Dernière intervention
4 mai 2013
53
Salam,

Si vous voulez savoir le temps d'exécution de votre programme, enregistrez l'heur dans une variable temp1 au début du programme et faite la même chose à la fin avec une autre variable temp2, et faîte la soustraction:

duree_prog=temp2-temp1


Allah mo3ine
Messages postés
81
Date d'inscription
mercredi 4 mai 2005
Statut
Membre
Dernière intervention
14 septembre 2007
8
Merci beacoup de ta réponse, je vais essayer de le mettre.
bonne journée.
Messages postés
3604
Date d'inscription
jeudi 16 juin 2005
Statut
Membre
Dernière intervention
3 juillet 2020
957
Sinon, une complexité, ça se calcule relativement facilement :)
Si tu nous donnais un aperçu de ton algorithme, on pourrait même s'amuser à la calculer ^^
Messages postés
1284
Date d'inscription
jeudi 7 décembre 2000
Statut
Contributeur
Dernière intervention
26 février 2009
168
ça c'est d'une naiveté. Si la complexité se calculait facilement, on ne s'embeterait pas à avoir une théorie de la complexité. Il y a pas mal d'algo ou on ne sait pas calculer la complexité, meme au pire des cas.
Messages postés
4100
Date d'inscription
jeudi 7 avril 2005
Statut
Contributeur
Dernière intervention
2 septembre 2013
839 >
Messages postés
1284
Date d'inscription
jeudi 7 décembre 2000
Statut
Contributeur
Dernière intervention
26 février 2009

Reivax voulais dire plutot qu'on peut évaluer le degré de complexité d'un programme, et non la complexité elle même.

Messages postés
81
Date d'inscription
mercredi 4 mai 2005
Statut
Membre
Dernière intervention
14 septembre 2007
8
Salut;
voila un éxemple de programme pour lequel je veux calculer la compléxité.
#include<iostream>
#include<cmath>

using namespace std;

//***************déclaration des fonctions***********************************

double puis(double x, double y){
double z;
z=exp(y*log(x));
return z;
}

double fonct(double x, int i){
double y;
if(i==0) y=3*puis(x,0.3);
if(i==1) y=1;
if(i>1) y=0;
return y;
}
double uti(double x, int i){
double y;
if(i==0) y=log(x);
if(i==1) y=1./(x+.001);
return y;
}
double grad(double delta, double x, double z, double n, int j, double h){
double y;
y=-(exp((n-delta)*j*h))*x-z*h;
return y;
}
//******************************************************************************
int main(){

double delta,h,lambda,capifinal,utilite,ro,epsi,capi0,cd,cg,consom,cap,cap1,n;
int nb,m,ok,iter,compter,number,Maxiter,Maxcompter;
//***********************déclaration des données*******************************
FILE* Ecriture = fopen("donnees_E","w");
fprintf(Ecriture,"%lf %lf %lf %lf %lf %lf %d %lf %d %d",10000.,.8,20.,10.,0.01,10.,100,.08,200,500);
fclose(Ecriture);

FILE* Lecture = fopen("donnees_E","r");
fscanf(Lecture,"%lf %lf %lf %lf %lf %lf %d %lf %d %d",&capi0,&delta,&lambda,&capifinal,&ro,&epsi,&nb,&n,&Maxiter,&Maxcompter);
fclose(Lecture);
//*****************************************************************************
double* capi = new double [nb];
double* mu = new double [nb];
double** conso = new double* [Maxiter+1];
cg=0;cd=capi0;
capi[0]=capi0;

for(int i=0;i<Maxiter+1;i++) conso[i]=new double [nb];
compter=0;
cap1=capi[0];
h=1./(nb);
//***********************Dichotomie pour trouver la consommation initiale******
while(compter<Maxcompter and cap1-capifinal>epsi){
consom=(cg+cd)/2.;cap=capi[0];
for(int i=0;i<nb-1;i++)cap=cap+h*(fonct(cap,0)-n*cap-consom);
// printf("%lf\n",cap);
if(cap>capifinal){cg=consom;cap1=cap;}
else cd=consom;
compter++;
}
//******************************************************************************
//********************Déscente de gradient**************************************
for(int i=0;i<nb;i++)conso[0][i]=cg;
FILE* fich = fopen("utilite_E","w");
iter=0;

while(iter<Maxiter){
for(int i=0;i<nb-1;i++) capi[i+1]=capi[i]+h*( fonct(capi[i],0)-n*capi[i]-conso[iter][i]);
// printf("%d\n",iter);
// printf("%lf\n",conso[iter][1]);
// printf("%d\n",iter);

if(capi[nb-1]>capifinal){
utilite=0.;
mu[nb-2]=2.*lambda*(capi[nb-1]-capifinal);
for(int i=2;i<nb-2;i++) mu[nb-(i+1)]=mu[nb-i]*(1+h*0.9*puis(capi[i],-0.7)-h*n);

// for(int i=0;i<nb;i++) utilite+=h*exp((n-delta)*i*h)*uti(conso[iter][i],0);
utilite=h*exp((n-delta)*(nb-1)*h)*uti(conso[iter][nb-1],0);
for(int i=0;i<nb;i++) printf("%d %lf %lf\n",i,capi[i],conso[iter][i]);
// printf("%d,%lf\n",iter,conso[iter][nb-1]);
fprintf(fich,"\n%lf",utilite);
for(int i=0;i<nb;i++) conso[iter+1][i]=conso[iter][i]-ro*grad(delta,uti(conso[iter][i],1),mu[i],n,i,h);
// for(int i=0;i<6;i++) printf("%d,%lf\n",i,grad(delta,uti(conso[iter][i],1),mu[i],n,i,h));
}
else break;

iter++;
}
fclose(fich);
printf("i Capital Conso ");
printf("\n<< %d iterations de Dichotomie & %d iterations de Descente de Gradient >>\n\n",compter,iter);

//********************************************************************************
FILE* fich2 = fopen("consommation_E","w");
for(int j=0;j<nb;j++){
for(int i=0;i<Maxiter;i++)fprintf(fich2,"%lf ",conso[i][j]);
fprintf(fich2,"\n");
}
fclose(fich2);
FILE* fich3 = fopen("capital_E","w");
for(int j=0;j<nb;j++) fprintf(fich3,"%lf\n",capi[j]);
fclose(fich3);
//*********************Sorties graphiques******************************************
FILE* capsci = fopen("capital_E.sci","w");
fprintf(capsci,"x=read('capital_E',%d, 1);\n",nb);
fprintf(capsci,"xtitle(\"lambda=%lf ",lambda);
fprintf(capsci,"delta=%lf ",delta);
fprintf(capsci,"n=%lf ",n);
fprintf(capsci,"capifinal=%lf ",capifinal);
fprintf(capsci,"ro=%lf ",ro);
fprintf(capsci,"capi[0]=%lf \",'t','€');\n" ,capi[0]);
fprintf(capsci,"v=[1:%d];\n",nb);
fprintf(capsci,"plot2d(v,x,[2,%d+1]);\n",nb);
fprintf(capsci,"legends(['CAPITAL'],2,5);\n");//Pour ajouter le titre
fclose(capsci);

FILE* utilisci = fopen("utilite_E.sci","w");
fprintf(utilisci,"x=read('utilite_E',%d,1);\n",iter);
fprintf(utilisci,"xbasc();\n");
fprintf(utilisci,"xtitle(\"lambda=%lf ",lambda);
fprintf(utilisci,"delta=%lf ",delta);
fprintf(utilisci,"n=%lf ",n);
fprintf(utilisci,"capifinal=%lf ",capifinal);
fprintf(utilisci,"ro=%lf ",ro);
fprintf(utilisci,"capi[0]=%lf \",'t','€');\n" ,capi[0]);
fprintf(utilisci,"v=[1:%d];\n",iter);
fprintf(utilisci,"plot2d(v,x,3);\n");
fprintf(utilisci,"legends(['BIEN ÊTRE ECONOMIQUE'],3,5);\n");
fclose(utilisci);

FILE*consosci = fopen("consommation_E.sci","w");
fprintf(consosci,"x=read('consommation_E',%d,%d);\n",nb-1,iter);
fprintf(consosci,"xbasc();\n");
fprintf(consosci,"xtitle(\"lambda=%lf ",lambda);
fprintf(consosci,"delta=%lf",delta);
fprintf(consosci,"n=%lf ",n);
fprintf(consosci,"capifinal=%lf ",capifinal);
fprintf(consosci,"ro=%lf ",ro);
fprintf(consosci,"capi[0]=%lf \",'t','€');\n" ,capi[0]);
fprintf(consosci,"for i=1:%d\n",iter);
fprintf(consosci,"y=x(:,i);\n");
fprintf(consosci,"v=[1:%d];\n",nb-1);
fprintf(consosci,"plot2d(v,y,i);\n");
fprintf(consosci,"end\n");
fprintf(consosci,"xset('color',2);plot2d(v,y,[-3:97]);\n");
fprintf(consosci,"legends(['CONSOMMATION OPTIMALE'],-3,5);\n");
fclose(consosci);
//*********************************************************************************
getchar();

return 0;
}



bon courage. et merci beaucoup.
La complexité d’un programme ou plus précisément d’un algorithme ne se calcule pas ni par le temps d’exécution nécessaire en unité de temps (secondes ou minutes…) pour aboutir à une solution et de cops atteindre la fin d’un programme ni par le nombre de ligne dans un programme.
Mais :
Le temps d’exécution d’un programme en utilisant l’unité de temps dépend de la machine utilisée, vitesse de processeur si vous voulez, donc on peut dire que pour le même programme on peut trouver mille résultats (durée) déférentes et cela selon, comme je vous ai dit au paravent, le type de la machine utilisée (P4 : 3.0, 2.8, …, P3 1.2, 1.0 GHz…).
C’est pour ça on fait recoure à ce qu’on appel la complexité algorithmique qui se calcule par le nombre d’opération nécessaire en fonction de la taille des données d’un problème donné (solution d’une équation, inverse d’une matrice, problème d’optimisation…).

Par exemple:
Nombre d’opération N=2n²
La taille des données T=n
La complexité C=2T² donc l’algorithme, ou programme est polynomial. Et comme vous voyez la complexité d’un programme dépend que de la taille de problème.
Si vous voulez plus de détails n’hésiter pas de poser vos questions et mettez devant la question [RO] = Recherche Opérationnelle.


_/ôô\_
Messages postés
81
Date d'inscription
mercredi 4 mai 2005
Statut
Membre
Dernière intervention
14 septembre 2007
8
merci beaucoup