Détermination de compléxité (en temps) d'un algorithme

Bonjour,
Voila une citation que j'ai trouvée sur le net et j'aimerais avoir votre avis :

Citation:

---

Complexité
Étant donné un algorithme, nous appelons opérations élémentaires :
· un accès en mémoire pour lire ou écrire la valeur d’une variable ou d’une case d’un
tableau ;
· une opération arithmétique entre entiers ou entre réels : addition, soustraction,
multiplication, division, calcul du reste dans une division entière ;
· une comparaison entre deux entiers ou deux réels.
Exemple : si on considère l’instruction c ¬ a + b, on peut compter quatre opérations
élémentaires :
· l’accès en mémoire pour lire la valeur de a,
· l’accès en mémoire pour lire la valeur de b,
· l’addition de a et b,
· l’accès en mémoire pour écrire la nouvelle valeur de c.
Pour un problème donné, on appelle instance tout jeu de données de ce problème. Par
exemple, pour un problème de tri, on obtient une instance en spécifiant la valeur numérique
des nombres à trier.

---

Ils ont certainement raison!; néanmoins ce qui me gène, c'est le fait d'attribuer (approximativement) le même temps d'exécution à une lecture en mémoire, écriture en mémoire, addition, soustraction,.... pour déterminer la complexité de l'algorithme. Personnellement, j'ai beaucoup travaillé dans le domaine de l'informatique industriel et je me rends compte facilement ce qui se passe au bas niveau, du point de vue composants!!. J'ai donc du mal à admettre cette idée d'opération élémentaire avec laquel raisonne les informaticiens au niveau algorithmique.
C'est certainement fiable; mais alors sur quelles argumentations s'appuie -t- on ?
Merci à vous

Citation:

---

Envoyé par wafiwafi

C'est certainement fiable; mais alors sur quelles argumentations s'appuie -t- on ?

---

Elémentaire mon cher Watson :lol:


En général il est quasi impossible (à moins d'y consacrer plus de temps qu'à établir l'algorithme) , d'évaluer le nombre exact d'opérations élémentaires, pour tout algorithme un tantinet complexe.


De plus, différentes architectures peuvent traiter différemment diverses opérations élementaires (floating-point arithmétique, par exemple, ou parallèlisme matériel, ou cablage sur certaines cartes), et même ceci peut être différent en fonction de la taille mémoire (swap par exemple), ou du type de la mémoire. Il est donc pour le moins délicat d'établir le temps d'une opération dite élementaire sans tenir compte de l'architecture matérielle, et donc d'établir un étalon général.


En conséquence, la notion de complexité en terme d'opérations élémentaires d'une part est extrêmement complexe en général et d'autre part a relativement peu d'intérêt générique d'étalon, à moins qu'on n'enlève les opérations de mouvement mémoire et qu'on ne se restreigne qu'aux +, -, *, /.


ça ne veut pas dire qu'on ne peut pas le faire (via des outils automatiques d'analyse), ou pour un algo simple, mais par exemple les outils automatiques auront beaucoup de mal à évaleur (impossible réellement) des itérations avec condition d'arrêt (par exemple une dichotomie) en termes d'opérations élémentaires.

Le concept important dans la complexité est la façon dont le temps augmente quand le nombre de données devient grand. Si tu as le choix entre N multiplications et N² accès mémoire, la 2e solution deviendra vite mauvaise si N croit.
L'ordre de l'algo (ici 1 ou 2 ) est la première chose à prendre en considération si tu travailles avec beaucoup de données si tu veux optimiser un calcul, ou le rendre possible.
Les autres facteurs dépendent du matériel etc.

Merci pour vos réponses.
On va dire que cela donne UNE IDÉE sur la façon avec laquelle l'algorithme peut virer au vinaigre.
Houiii, pourquoi pas! mais c'est osé!

Encore pire! quand on travaille avec une structure de données dont on ignore complétement l'implantation. Dans ce cas, privilège -t- on l'utilisation de la structure ou la complexité de l'algorithme.
Tout ceci peut bien faire l'objet d'un travail de recherche dans un laboratoire informatique!!!
Cordialement

nul besoin de recherches dans un laboratoire à ce propos, laissons les travailler sur des choses beaucoup plus essentielles.

pour ce qui est de la complexité du code VS temps d'exécution, les circuits conventionnels de développement suffisent amplement.

il apparait logique lorsque l'on travaille sur les ports d'entrées/sorties que les temps d'exécutions soient allongés.
il apparait plus que logique que les opérations sur la mémoire soient plus lentes que sur les registres.

déterminer la complexité (en temps) d'un algorithme peut être estimée, mais ne donnera pas de valeur exacte, et il se peut même que ce ne soit pas vraiment utile de se pencher sur ce genre de détails, étant donné que le but d'une machine est d'exécuter, quelle que soit la complexité, du code qui sera vu au niveau machine comme une simple succession d'instructions élémentaires.

Citation:

---

les circuits conventionnels de développement suffisent amplement.

---

reposent sur des tests (validés par des statistiques)! néanmoins tu as raison sur le fond.
Merci à toi

Citation:

---

Envoyé par wafiwafi

Merci pour vos réponses.
On va dire que cela donne UNE IDÉE sur la façon avec laquelle l'algorithme peut virer au vinaigre.
Houiii, pourquoi pas! mais c'est osé!

Encore pire! quand on travaille avec une structure de données dont on ignore complétement l'implantation. Dans ce cas, privilège -t- on l'utilisation de la structure ou la complexité de l'algorithme. Tout ceci peut bien faire l'objet d'un travail de recherche dans un laboratoire informatique!!!
Cordialement

---

Suivant les cas, l'utilisation de telle ou telle structure peut donner lieu à un nouvel algorithme améliorant la complexité...


De manière générale (voir ici-même les cours d'algo et sur Wiki les difféents chapitres s'y référant "Computational Complexity"), un algo est surtout limité par la manière de calculer, c'est à dire l'algorithmique.

Il peut s'avérer que dans certains cas utiliser telle ou telle structure re-définisse un nouvel algo plus efficace pour obtenir la même chose. Dans ce cas-là, il y aura bien une influence.

Mais prenons un exemple : un tri quick-sort

Quelles que soient les choses à trier, le principe amène à une complexité moyenne en O(N logN), et une complexité maximale en O(N2)


Le facteur important est l'évaluation que l'on peut faire en fonction de la taille de l'entrée.

Que ce soit pour 1 point ou pour N points, l'algorithme utilisera toujours les mêmes opérations, et donc le même nombre d'opérations élémentaires.

A un facteur multiplicatif près, c'est donc le lien entre la taille de l'entrée et le temps de calcul qui est important, pas le nombre exact d'opérations.



La mesure n'est pas sur un temps absolu (comme mentionné cela n'a aucun intérêt) mais sur un temps relatif..


Si je double le nombre de points en entrée, est-ce que je double le temps de calcul ? est-ce que il est proprotionnel au carré du nombre de points ? à une puissance supérieure ? au logarithme ?


C'est la question la plus importante dans la fabrication des algoithmes....



Idéalement, et quel que soit ce qu'on veut faire, on aimerait bien que ce soit proportionnel.... ce qui arrive rarement :aie:




Prenons un autre exemple où là, la structure peut intervenir :

Soit un tableau A de N cases

Si je veux décaler le tableau de 3 cases :

Soit il me faudra un tampon de 3 "sauvegardes", plus une boucle de N-3, soit il me faudra 3 boucles de N-1

Déjà là, algorithmiquement, on 2 solutions avec des complexités différentes, bien qu'en terme symboliques elles s'expriment pareillement O(N)


Mais si maintenant je remplace le tableau par une liste doublement chaînée, je n'ai plus que 4 opérations à faire : dire que le pprécédent du 4ième élement est vide, dire que le suivant du 3ième est vide, dire que le suivant du dernier est le premier et que le précédent du premier est le dernier.

Donc ici, avec une structure différente, je suis passé d'un algo en O(N), c'est à dire proprotionnel au nombre de points, en un algo en O(1), c'est à dire à temps constant quelle que soit la taille de l'entrée..

Et peu importe que pour ces 4 opérations il faille 23000 opérations élémentaires... C'est indépendant du nombre d'entrées...

Citation:

---

Envoyé par wafiwafi

Personnellement, j'ai beaucoup travaillé dans le domaine de l'informatique industriel et je me rends compte facilement ce qui se passe au bas niveau, du point de vue composants!!. J'ai donc du mal à admettre cette idée d'opération élémentaire avec laquel raisonne les informaticiens au niveau algorithmique.

---

La complexité d'un algorithme n'a de sens qu'au niveau "algorithmique" (écriture en pseudo code). Cette complexité sert à départager des algorithmes entre-eux.

En aucun cas cette complexité ne peut servir à mesurer (ou meme estimer) un temps de calcul. Notamment car le "pseudo code" est souvent un langage impératif simpliste censé s'exécuter sur un monoprocesseur, alors que la réalité actuelle est tout autre (langages spécifiques, processeurs dédiés, architectures parallèles, ...)

Que des réponses pertinentes!
Les choses sont au clair.
Merci à vous