Et aussi, ça me semble bizarre que ce soit le tri par tas que l'on utilise pour les petits tableaux. Tu ne voulais pas dire tri par insertion ? [edit] Vanyali > Tu as dit que le tri par tas est le tri fusion dérécursifié. C'est un peu la même idée (diviser pour réger), mais ce n'est pas le même algo (encore faudrait-il définir l'égalité de deux algorithmes...) [edit bis] Question passionnante par ailleurs, définir l'égalité (ou, autre formulation : repérer les symétries). Regardez la théorie des catégories. Ça permet de repérer la symétrie entre le test conditionnel et le produit cartésien (ce que vous faites quand vous définissez une classe/structure qui contient un entier et un flottant par exemple). Ces deux choses sont donc deux aspects d'un même objet. Surprenant, n'est-ce pas !? (Mizur, c'est de ce genre de choses que je parle quand je dis « Mathématiques », pas d'ésotérisme inutile et stérile) Si vous voulez des références, demandez. Mizur > Les algos de tri exponentiels, ça existe, mais c'est une blague, bien sûr (cf. Hanoï sort). Et il faut remplacer dans ton premier post sur le topic logarithmique par quasi-linéaire et linéaire par quadratique. Tu dis aussi « Pas d'accord ! Par définition les temps de calculs sont forcément plus courts avec du log(N) (pour N données traitées) que du N² par exemple (pour des exemples de tri standards) non ? » (je vois mal un algo traitant N données en temps logarithmique) Et en fait, ce qui est vrai, c'est que la complexité donne le temps d'exécution asymptotique (quand les valeurs deviennent arbitrairement grandes). Donc un algo en N² peut être plus rapide qu'un algo en NlnN (exemple du tri par insertion qui est le plus rapide pour les petits tableaux). Ensuite, dans la plupart des langages (pas ceux qui optimisent la tail-recursion comme les fonctionnels), je confirme qu'un algo récursif est plus lent que le même algo en itératif. |
