[Complexité] Question stupide :)

Citation:

---

Envoyé par souviron34

Il me semble quand même que, dans l'absolu, 2 est plus lent que 1...
Et que donc 2 algos en O(N) peuvent quand même avoir des différences considérables (là, il y a juste un facteur , mais entre faire 2 fois N et 10 000 fois N, c'est pas pareil..)

---

Effectivement ca peut être considérable en temps d'exécution. Mais c'est pas trop ce qui importe dans l'étude théorique.

En complexité algorithmique, ce qui nous importe c'est de savoir si ton algo dépend de la taille des données (N), de l'ordre de grandeur des données (log(N)), des appariements possibles des données (N²), des permutations possibles des données (N!), ...

En fait, au-delà de la théorie, si l'on veut comparer 2 algorithmes sans comparer des implémentations, nous ne pouvons pas affiner davantage...

Par exemple sur un processeur à structure parallèle, l'exécution de

Code:

---

1 2 3 4

for ( i = 0 ; i < 1000 ; i++ ) { d = sqrt(x2+y2); }

---

sera de durée similaire que

Code:

---

1 2 3 4 5 6 7 8 9

for ( i = 0 ; i < 1000 ; i++ ) { d = sqrt(x2+y2); d2 = sqrt(x2+y2); d3 = sqrt(x2+y2); d4 = sqrt(x2+y2); d5 = sqrt(x2+y2); d6 = sqrt(x2+y2); }

---

contrairement à si l'on était sur un processeur à structure sérielle.

La liste des biais d'implémentation est longue (call stack, optimisations du compilateur, type de processeurs, coût d'un accès mémoire, etc).

Par contre, si un algorithme est Θ(n) et un autre Θ(n²) alors dès que les inputs seront un peu grands, sauf peut-être exception, l'implémentation du premier algorithme sera toujours plus rapide que celle du second.

merci à vous pour l"effort :)

Et désolé d'être un peu long à la comprenette... :oops:

Tu es le bienvenu, et ces questions ne sont pas forcément triviales :)

Il ne faut pas demander à la notion de complexité plus que ce qu'elle veut dire :
Si je peux faire un calcul pour N données en un temps raisonnable, pourrai-je le faire pour 10*N, 100*N,...
Si on utilise un nombre fixe de données et qu'on veut pédaler vite, faire le test sera plus simple, plus rapide et plus fiable.

Attention à bien distinguer :

• le travail du concepteur d'algorithmes (analyse des complexités computationnelle et spatiale théoriques).
• le travail d'implémentateur d'algorithmes (optimisation de la complexité empirique de l'algorithme en fonction des environnements logiciel et matériel).
• le travail du développeur (choisir l'algorithme ainsi que l'implémentation les plus adaptés à son problème).

et quand on est les 3 ? :aie: :cry:

Citation:

---

Envoyé par souviron34

et quand on est les 3 ? :aie: :cry:

---

C'est encore plus complexe. :aie:

y'a une formule ou un symbole ? :aie:

Il me semble que la fonction pour exprimer cette complexité prend en paramètre la motivation du développeur et surtout le temps/budget dont il dispose... un coup de master theorem dessus et le tour est joué :ccool:

Citation:

---

Envoyé par souviron34

y'a une formule ou un symbole ? :aie:

---

Oui, on utilise la notation ?(N), qu'on appelle le PourquoiTant de N

:dehors:

Joli :bravo:

Une preuve de plus qu'en mathématiques, plus les formules sont courtes, plus elles sont efficaces :fou: