Compléxité.
Résolu
abdeloihab
Messages postés
76
Date d'inscription
Statut
Membre
Dernière intervention
-
abdeloihab Messages postés 76 Date d'inscription Statut Membre Dernière intervention -
abdeloihab Messages postés 76 Date d'inscription Statut Membre Dernière intervention -
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.
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
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
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
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 ^^
Si tu nous donnais un aperçu de ton algorithme, on pourrait même s'amuser à la calculer ^^
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.
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.
_/ôô\_
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.
_/ôô\_
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question