Non, pas du tout. D'ailleurs, on peut faire un tri en mieux que n log n, sous certaines contraintes.
Et ? Dans le cas général, on ne peut pas faire mieux que n log n, ce qui donne bien un temps minimal, il suffit de traduire ça en terme de cycle d'horloge.
Je ne vois pas en quoi la complexité théorique d'un problème change le choix que tu feras entre des algorithmes de complexités pratiques connues.
Moi non plus, je ne parle pas de ça. En effet, je fais référence à certains résultats comme par exemple le coût de n log n pour le tri qui se traduit par des bornes comparables pour le calcul d'enveloppe convexe et d'une façon détournée par des bornes pour les triangulations de delaunay. Comme on sait maintenant qu'on ne peut pas faire le calcul en mieux que n^{d/2} (d est la dimension de l'espace), on cherche des algorithmes qui calculent des approximations de la solution, alors qu'on perdrait notre temps à chercher des algos exacts si on ne connaissait pas la borne...
Certes. Mais les gens qui travaillent sur toute une partie de l'algorithmique n'ont pas comme objectif la résolution de problèmes informatiques précis, je pense. Je suis bien d'accord qu'il y a toujours des retombées potentielles (comme avec n'importe quelle branche des maths).
Ca prouve juste que tu te trompes. Je connais pas mal de gens qui bossent en algorithmique et c'est très souvent avec des motivations pratiques, parfois lointaines, il est vrai.
Ce sont des (ensembles de) techniques informatiques.
Ouarf ! Je ne comprends pas ce que tu veux dire par technique.
[^] # Re: Droit d'auteur et travailleurs
Posté par boubou . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
Et ? Dans le cas général, on ne peut pas faire mieux que n log n, ce qui donne bien un temps minimal, il suffit de traduire ça en terme de cycle d'horloge.
Je ne vois pas en quoi la complexité théorique d'un problème change le choix que tu feras entre des algorithmes de complexités pratiques connues.
Moi non plus, je ne parle pas de ça. En effet, je fais référence à certains résultats comme par exemple le coût de n log n pour le tri qui se traduit par des bornes comparables pour le calcul d'enveloppe convexe et d'une façon détournée par des bornes pour les triangulations de delaunay. Comme on sait maintenant qu'on ne peut pas faire le calcul en mieux que n^{d/2} (d est la dimension de l'espace), on cherche des algorithmes qui calculent des approximations de la solution, alors qu'on perdrait notre temps à chercher des algos exacts si on ne connaissait pas la borne...
Certes. Mais les gens qui travaillent sur toute une partie de l'algorithmique n'ont pas comme objectif la résolution de problèmes informatiques précis, je pense. Je suis bien d'accord qu'il y a toujours des retombées potentielles (comme avec n'importe quelle branche des maths).
Ca prouve juste que tu te trompes. Je connais pas mal de gens qui bossent en algorithmique et c'est très souvent avec des motivations pratiques, parfois lointaines, il est vrai.
Ce sont des (ensembles de) techniques informatiques.
Ouarf ! Je ne comprends pas ce que tu veux dire par technique.