Discussion :

[Bool1988]

Bonjour,

Je me posais la question suivante: si l'on considère trois fonctions f,g,h, où g et h effectuent respectivement 1 et 2 opérations (temps constant), et f est la fonction suivante:

let f machin=
........
for i=1 to n do
g machin;
h machin;
done;
.............

la fonction f appelle donc n fois la fonction g et h; j'aurais donc tendance à penser que l'ordre de grandeur (c'est-à-dire un équivalent du temps mis par la fonction) de f est n*(2+1)=3n. Pourtant, j'ai vu à plusieurs reprises dans des corrections que l'ordre de grandeur de la fonction f était 2n: la règle semblant être de considérer la fonction appelée la plus coûteuse (ici h) et de multiplier par n. Pouvez-vous m'expliquer ce mystère? Merci d'avance!

[Jedai]

Ca me parait un peu bizarre ton histoire... Généralement pour un calcul de complexité, soit on néglige les constantes et ta fonction est en O(n), soit on essaie d'être vraiment précis et on trouve du 3n.
Par ailleurs l'"ordre de grandeur" d'une fonction ne veut pas dire grand chose (sauf si on parle de son résultat), tu veux parler de l'ordre de grandeur de la complexité d'une fonction.

--
Jedaï

[alex_pi]

Tu es sûr que tu n'as pas une fonction en n et l'autre en n^2, et que là effectivement, tu négliges celle en n, et qu'au final c'est en n^3 ? Parce que dans l'autre cas, je me joins à Jedai pour dire que ça m'étonne fortement !

[InOCamlWeTrust]

C'est un raisonnement que certaines personnes tiennent, notament des gens issus du domaine du calcul scientifique : dans leur cadre de travail, il s'agit de considérations pertinentes. Le problème, c'est que trop de gens reprennent ces mêmes arguments et racontent des conneries.

Comme on te le dit, on oublie les constantes, parce que ça ne veut rien dire.

Une complexité temporelle ne mesure qu'une évolution du temps de calcul en fonction d'une taille caractéristique des données en entrée : POINT A LA LIGNE. Tout autre sens est faux ou idiot.

[SpiceGuid]

Mon anecdote à propos de la complexité, dans un excellent ouvrage spécialisé sur le sujet l'auteur disait avoir implémenté la multiplication Knuth-Karatsuba, et il expliquait sa déception: finalement il constatait que (en base 10) pour des nombres inférieurs à environ 16000 décimales la multiplication naïve battait la multiplication Karatsuba à tous les coups et donc, selon lui, l'algorithme méritait d'être connu mais n'avait qu'un d'intérêt pratique limité à des calculs extrêmes.

C'est le genre de choses qu'on peut lire dans les ouvrages des bibliothèques universitaires, dont les plus vieux datent parfois des années 1970.

En réalité, en s'appliquant un peu (ok: un peu mais très soigneusement) en OCaml la multiplication Karatsuba dépasse la multiplication naïve à partir de seulement 22 à 25 décimales. L'évolution des performances, des langages et des compilateurs a déplacé le seuil de rentabilité de la multiplication Karatsuba. En outre, plus une machine est puissante plus n est grand, et plus n est grand plus on a intérêt à utiliser un algorithme efficace.

Moralité: O(..) ça veut toujours dire qu'on se fiche des constantes.

[InOCamlWeTrust]

En outre, plus une machine est puissante plus n est grand, et plus n est grand plus on a intérêt à utiliser un algorithme efficace.

Ouh laaaaa garçon ! C'est la raison qui parle, là... le problème, c'est que les langages utilisés sont de plus en plus miteux, avec l'avènement de Java et autres... donc le programme qui prenait hier 3 secondes avec un ordinateur pourri prendra toujours 3 secondes aujourd'hui avec une machine de course, à cause d'une implantation désastreuse dans un de ces sous-produits de langages de programmation...

Sinon, je suis d'accord : la meilleure façon d'accélérer un programme, c'est d'utiliser de meilleurs algorithmes !

[Jedai]

Ouh laaaaa garçon ! C'est la raison qui parle, là... le problème, c'est que les langages utilisés sont de plus en plus miteux, avec l'avènement de Java et autres... donc le programme qui prenait hier 3 secondes avec un ordinateur pourri prendra toujours 3 secondes aujourd'hui avec une machine de course, à cause d'une implantation désastreuse dans un de ces sous-produits de langages de programmation...

Je ne pense pas que le problème soit là, il est certain que des langages bien plus "lourd" sont aujourd'hui employés en lieu et place du C (ou éventuellement du C++), néanmoins je crois que s'il n'y avait que ça, on aurait tout de même de meilleures performances. La principale raison de cette curieuse stagnation des performances des programmes alors que les machines sont de plus en plus puissantes est plus à chercher à mon avis dans une tentation de plus en plus grande de se contenter du premier algorithme ou structure de donnée qui donne des performances acceptables sur une machine actuelle là où auparavant un programmeur faisait de son mieux pour trouver le meilleur algorithme et se mijotait ses structures de données aux petits oignons (pas pour dire qu'il était beaucoup plus consciencieux, mais il n'avait guère le choix s'il voulait obtenir un produit utilisable).

--
Jedaï

[InOCamlWeTrust]

Oui oui oui, bien-sûr... mais je parlais, implicitement, à algorithme égal (structures de données et code).