Comment mesure t-on l'efficacité d'un algorithme ?

[invite4492c379]

J en doute fort vu que vous avez choisi le cas le plus défavorable et que même dans ce cas je bats l algo école

Ce n'est pas un combat

Je vais t'expliquer pourquoi on dit que la multiplication naïve (celle de l'école) est en O(n²). Je note cette multiplication par X, et je considère un nombre M de m chiffres et un nombre N de n chiffres. On peut prendre M>N sans perdre en généralité. M et N sont codés en notation décimale, par convention je prends où chaque est un chiffre.

Je note la complexité de cet algorithme par C(X(m,n)).

Multiplier deux chiffres ou ajouter deux chiffres sont des opérations élémentaires. Cela signifie que leur coût est une constante. Faire 9x9 ou 7+8 prends le même temps. Si on formalise on a simplement C(X(1,1)) et C(+(1,1)) sont en O(1). Accéder à un chiffre d'un nombre est aussi en O(1). Si tu ne comprends pas la notation grand O google un coup.

Il n'est pas difficile de comprendre qu'additioner deux nombres M et N revient en fait à créer un nombre d'au plus m+1 chiffres en additionnant chiffres à chiffres les nombres, cela signifie que C(+(m,n)) est en O(m). Je pense qu'il est tout aussi compréhensible que multiplier un nombre M par un chiffre demande m multiplications, soit C(X(m,1)) est en O(m).

X est un algo simple, j'obtiens n nombres (en multipliant M par chaque chiffres de N) d'au plus m+1 chiffres que j'additionne entre eux, soit



soit C(X(m,n)) est en O(mn).


Prenons maintenant ton algo que je vais noter Y.
Dans un premier temps tu construis une table de 10 éléments qui correspondent à 0xM, 1xM, ..., 9xM.
Tu obtiens ensuite n nombres (en faisant un lookup sur ta table, cela peut se faire en temps constant) d'au plus m+1 chiffres que tu additionnes entre eux, soit



soit C(Y(m,n)) est en O(mn).

LEs deux algorithmes ont donc le même comportement en général et sont aussi bon (ou mauvais suivant le point de vue) que l'autre. Ce qui «rend» leur comportement mauvais est le fait qu'il y a obligatoirement la phase «j'additionne n nombres de m chiffres». Il est clair que créer un table est intéressant, ça va un peu plus vite surtout si on ne connaît pas les tables de multiplication. Néanmoins, cette étape nécessite un espace en O(m) pour Y, alors que la version X est en O(1). D'un point de vue implémentation, cela nécessite pour chaque calcul la création de cette table, c'est lourd.

Mais il est clair que selon ta définition ton algo est très utile pour les cas favorables ... d'ailleurs que donnerait ton algo pour des nombres codés en base 2 ?
-----

[invite501e8040]

d'ailleurs que donnerait ton algo pour des nombres codés en base 2 ?

La question piège

[invitefd4e7c09]

Prenons maintenant ton algo que je vais noter Y.
Dans un premier temps tu construis une table de 10 éléments qui correspondent à 0xM, 1xM, ..., 9xM.

C'est la que vous vous trompez car je construis une table d'au plus 4 éléments : 1*M, 2*M, 4*M et 8*M

En guise de conclusion et en dépit de tous les arguments et la bonne foi dont j'ai pu faire preuve (cf la multiplication proposé par Médiat que je me suis tapé à la main), je vous mets au défi de mettre à mal l'algorithme de l'addition face à l'algorithme de l'école au travers un exemple quel qu'il soit.

[invite4492c379]

Comme je te l'ai dit ... selon tes critères, ta solution est la meilleure sur les nombres qui conviennent le mieux à ta méthode, je te l'accorde.

Si tu utilises la notion de complexité telle qu'elle est définie et utilisée, ton algo a une complexité en n², la même complexité en temps que l'algorithme école, et une complexité supérieure en espace.

[invite4492c379]

C'est la que vous vous trompez car je construis une table d'au plus 4 éléments : 1*M, 2*M, 4*M et 8*M
(...)

Désolé, j'ai optimisé ta méthode pour la rendre plus générale ...
Malheureusement, en utilisant les critères classiques de complexité algorithmique, ce n'est pas cette partie qui est la plus coûteuse ...

[invitefd4e7c09]

Désolé, j'ai optimisé ta méthode pour la rendre plus générale ...
Malheureusement, en utilisant les critères classiques de complexité algorithmique, ce n'est pas cette partie qui est la plus coûteuse ...

Pour le point de vue informatique, vous devez avoir raison cela semble être du même acabit que l'algorithme de l'école.
Dans la pratique, j'attends encore l'exemple mettons à mal l'algo de l'addition face à celui de l'école.

[invite4492c379]

Ma question a l'origine portait également sur l'efficacité de l'algo (chose que je suis incapable de mesurer).
(...)

Je t'ai expliqué comment ça se mesure, et ma réponse est étayée.
Maintenant si tu définis tes propres critères cela ne concerne plus que toi.

Pour le point de vue informatique, vous devez avoir raison cela semble être du même acabit que l'algorithme de l'école.
Dans la pratique, j'attends encore l'exemple mettons à mal l'algo de l'addition face à celui de l'école.

Pas informatique ... algorithmique.

[inviteea028771]

Pour le point de vue informatique, vous devez avoir raison cela semble être du même acabit que l'algorithme de l'école.
Dans la pratique, j'attends encore l'exemple mettons à mal l'algo de l'addition face à celui de l'école.

Le problème c'est que la pratique, c'est l'informatique... plus personne ne s'amuse à multiplier les grands nombres à la main.

Même si votre algorithme nécessitait cinq fois moins d'opérations que l'algorithme naïf classique, il ne serrait toujours pas intéressant de ce point de vue là. C'est tout au plus une curiosité.

[Médiat]

je vous mets au défi de mettre à mal l'algorithme de l'addition face à l'algorithme de l'école au travers un exemple quel qu'il soit.

Ce n'est pas à vous de nous mettre au défit, c'est à vous de le démontrer !

[invitefd4e7c09]

Je vous le concède vous m'avez éclairé l'esprit sur l'aspect algorithmique de cette affaire.
Vous avez argumenté formidablement (cf toutes les lignes que vous avez rédigé) en vous heurtant parfois à l'opiniâtreté dont j'ai pu faire preuve
Après cela, l'approche algorithmique est une approche parmi tant d'autre. Pour ma part je déplore le fait qu'il faille prendre le cas le plus défavorable dans cette approche.
D'autre part, cette approche est tellement décalé par rapport à la réalité du terrain (celle du papier et crayon). Prenons les premières décimales de et multiplions les avec les suivantes et vous verrez qu'on est loin, très loin des considérations de "cas le plus défavorable".

En conclusion, je vais encore être de mauvaise foi et vous dire que dans la réalité, on multiplie que trop rarement des entiers ne contenant aucun chiffres étant une puissance de (cf entre autre la loi de Benford ou tout simplement la répartition des chiffres dans les décimales de )

[invite4492c379]

Je vous le concède vous m'avez éclairé l'esprit sur l'aspect algorithmique de cette affaire.
Vous avez argumenté formidablement (cf toutes les lignes que vous avez rédigé) en vous heurtant parfois à l'opiniâtreté dont j'ai pu faire preuve
Après cela, l'approche algorithmique est une approche parmi tant d'autre. Pour ma part je déplore le fait qu'il faille prendre le cas le plus défavorable dans cette approche.

Disons que le pire des cas permet de majorer et de savoir à quoi s'attendre. Cela permet aussi de savoir quelles sont les limites.

D'autre part, cette approche est tellement décalé par rapport à la réalité du terrain (celle du papier et crayon). Prenons les premières décimales de et multiplions les avec les suivantes et vous verrez qu'on est loin, très loin des considérations de "cas le plus défavorable".

Elle n'est pas décalée, au contraire. La multiplication école est a priori la mieux adaptée à l'enseignement, tel qu'il est pratiqué actuellement. Les calculateurs prodiges ne l'utilisent certainement pas.

En conclusion, je vais encore être de mauvaise foi et vous dire que dans la réalité, on multiplie que trop rarement des entiers ne contenant aucun chiffres étant une puissance de (cf entre autre la loi de Benford ou tout simplement la répartition des chiffres dans les décimales de )

Hum, on multiplie rarement des nombres qui ne comportent que des puissances de 2

[invitefd4e7c09]

Hum, on multiplie rarement des nombres qui ne comportent que des puissances de 2

Excellent !

[invitefd4e7c09]

Ce n'est pas à vous de nous mettre au défit, c'est à vous de le démontrer !

Grincheux va