Compléxité.
Résolu/Fermé
abdeloihab
Messages postés
76
Date d'inscription
mercredi 4 mai 2005
Statut
Membre
Dernière intervention
12 septembre 2007
-
27 oct. 2006 à 14:33
abdeloihab Messages postés 76 Date d'inscription mercredi 4 mai 2005 Statut Membre Dernière intervention 12 septembre 2007 - 9 nov. 2006 à 16:22
abdeloihab Messages postés 76 Date d'inscription mercredi 4 mai 2005 Statut Membre Dernière intervention 12 septembre 2007 - 9 nov. 2006 à 16:22
5 réponses
hamzafes
Messages postés
243
Date d'inscription
lundi 26 juin 2006
Statut
Membre
Dernière intervention
4 mai 2013
54
28 oct. 2006 à 18:37
28 oct. 2006 à 18:37
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
abdeloihab
Messages postés
76
Date d'inscription
mercredi 4 mai 2005
Statut
Membre
Dernière intervention
12 septembre 2007
9
30 oct. 2006 à 11:32
30 oct. 2006 à 11:32
Merci beacoup de ta réponse, je vais essayer de le mettre.
bonne journée.
bonne journée.
Reivax962
Messages postés
3671
Date d'inscription
jeudi 16 juin 2005
Statut
Membre
Dernière intervention
11 février 2021
1 011
30 oct. 2006 à 11:56
30 oct. 2006 à 11:56
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 ^^
tafiscobar
Messages postés
1277
Date d'inscription
jeudi 7 décembre 2000
Statut
Contributeur
Dernière intervention
26 février 2009
177
2 nov. 2006 à 16:30
2 nov. 2006 à 16:30
ç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.
kij_82
Messages postés
4088
Date d'inscription
jeudi 7 avril 2005
Statut
Contributeur
Dernière intervention
30 septembre 2013
857
>
tafiscobar
Messages postés
1277
Date d'inscription
jeudi 7 décembre 2000
Statut
Contributeur
Dernière intervention
26 février 2009
2 nov. 2006 à 16:41
2 nov. 2006 à 16:41
Reivax voulais dire plutot qu'on peut évaluer le degré de complexité d'un programme, et non la complexité elle même.
abdeloihab
Messages postés
76
Date d'inscription
mercredi 4 mai 2005
Statut
Membre
Dernière intervention
12 septembre 2007
9
30 oct. 2006 à 15:58
30 oct. 2006 à 15:58
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
abdeloihab
Messages postés
76
Date d'inscription
mercredi 4 mai 2005
Statut
Membre
Dernière intervention
12 septembre 2007
9
9 nov. 2006 à 16:22
9 nov. 2006 à 16:22
merci beaucoup
