Discussion :

[marchand_de_sable]

Bonjour à tous.

Je dois faire l'étude de complexité de mon application (ou plutôt, d'une partie de l'algo), mais je n'y connais pas grand chose.

Je me suis un peu documenté sur le sujet, mais il reste de grande zones d'ombres :
- les O, o, petit et grand oméga : représentent-ils des informations complémentaires, ou différents cas de complexité ?
- quelles "opérations fondamentales" prendre en compte ?


En effet, la base de l'algo est simple : c'est une itération sur les noeuds d'un arbre. A chaque noeud, je fais quelques opérations.
Mais dans les documents que j'ai lus, les exemples traités utilisent des types de données et d'opérations "simples". Les opérations fondamentales sont des comparaisons de valeurs, des calculs simples et des affectations de valeurs.. Mais quand on travaille sur des objets plus "complexes", ce type d'opérations arrivent dès l'instanciation de l'un d'eux, avant même qu'on les manipule !!
Donc en terme de complexité
int i <- 10
et
ObjetComp obj <- new ObjetComp(p1, p2);
ne peuvent pas être équivalents.

Faut-il alors définir l'instanciation d'un objet comme l'ensemble des opérations de plus bas niveau qu'il exige ? De même pour chaque fonctions ?

[j.p.mignot]

les O, o, petit et grand oméga

voir notations de Landau

par exemple
http://perso.orange.fr/megamaths/oral1/cfon0006.pdf

[Jean-Marc.Bourguet]

Faut-il alors définir l'instanciation d'un objet comme l'ensemble des opérations de plus bas niveau qu'il exige ? De même pour chaque fonctions ?

Oui.

[marchand_de_sable]

Ca va pas être une partie de plaisir...

Du coup, je reformule ma 2ème question, ce n'est pas "qelles opérations fondamentales prendre en compte", mais plutôt "quelles sont les opérations de plus bas niveau" ?
Par exemple :

a <- (b+c)/d

c'est 1, 2 ou 3 opérations ? (1 calcul ? 1 addition + 1 division ? 1 addition + 1 division + 1 affectation ?)

[Jean-Marc.Bourguet]

a <- (b+c)/d

c'est 1, 2 ou 3 opérations ? (1 calcul ? 1 addition + 1 division ? 1 addition + 1 division + 1 affectation ?)

C'est un nombre constant d'operations (du moins tant que b, c et d ne designent pas des entiers non bornes, des matrices ou autres choses qui feraient que le temps pour calculer a pourrait varier de maniere non bornee), c'est tout ce qui compte quand on parle de complexite.

[marchand_de_sable]

tout ce qui compte quand on parle de complexite.

J'ai encor bien du mal à faire la part des choses...

Mais ça vient petit à petit...

Sinon, autre question : quand des instructions dépendent d'une condition (dans un "si" ou un "tant que"), j'ai vu qu'on pouvait (devait ?) calculer les coûts min et max. Mais quand plusieurs conditions sont imbriquées, les valeurs trouvées risquent de ne plus avoir de lien avec les valeurs en pratique (par exemple, si on trouve des bornes min et max à 0 et + l'infini, on n'est pas bien avancé...)...Que doit-on faire dans ces cas-là ?

Et un dernier petit renseignement pour la route : tous les documents que j'ai trouvé ne parlent que de complexité en temps, mais rien sur la complexité en espace. Vous n'auriez pas des infos là-dessus ?

[Jean-Marc.Bourguet]

J'ai encor bien du mal à faire la part des choses...

Mais ça vient petit à petit...

Sinon, autre question : quand des instructions dépendent d'une condition (dans un "si" ou un "tant que"), j'ai vu qu'on pouvait (devait ?) calculer les coûts min et max. Mais quand plusieurs conditions sont imbriquées, les valeurs trouvées risquent de ne plus avoir de lien avec les valeurs en pratique (par exemple, si on trouve des bornes min et max à 0 et + l'infini, on n'est pas bien avancé...)...Que doit-on faire dans ces cas-là ?

Et un dernier petit renseignement pour la route : je n'est p

0 est une constante comme une autre

Quand le code dans les branches n'a pas une duree d'execution constante, il y a plusieurs approches. Prendre le pire des cas. Reussir a connaitre la repartition statistique et donc a avoir une duree d'execution "en moyenne".

[marchand_de_sable]

0 est une constante comme une autre

+ l'infini aussi ?

Quand le code dans les branches n'a pas une duree d'execution constante, il y a plusieurs approches. Prendre le pire des cas. Reussir a connaitre la repartition statistique et donc a avoir une duree d'execution "en moyenne".

C'est ce que j'avais vu...
Mais là encor, ça va être difficile de déterminer une répartition statistique qui soit représentative (je veux dire par là, qui ne soit pas dépendante d'un domaine spécifique dans lequel peut tourner mon appli...)

En tout cas, merci pour vos réponses.
Je vais essayer d'avancer avec tout ça.

Pour la complexité en espace, des infos ?

Encor merci.
A+