Dans le cas général, on ne peut pas faire mieux que n log n
Heu, on se préoccupe peu du cas général. En informatique il n'y a que des applications spécifiques à un domaine donné. Le rendu 3D "cheap", les calculs de routage ont longtemps utilisé des tris en O(n) en limitant la dynamique des valeurs considérées (radix sort).
ce qui donne bien un temps minimal, il suffit de traduire ça en terme de cycle d'horloge.
Et la constante multiplicative, et le caractère asymptotique du O(n log n), ils sont partis où ? Ton estimation de cycles d'horloge, elle ne veut rien dire si elle se base sur la complexité théorique du problème et non sur la complexité pratique d'un algorithme...
Ouarf ! Je ne comprends pas ce que tu veux dire par technique.
Disons : procédés appliqués à un domaine précis pour obtenir des résultats précis, et mis au point par la maturation progressive d'un savoir-faire. Contrairement à la recherche scientifique où l'objectif est l'élargissement de l'horizon intellectuel et théorique, non la résolution de problèmes concrets et immédiats. Note que certaines disciplines peuvent se situer à la frontière entre les deux (exemple : des résultats mathématiques sont mis à profit pour s'assurer de certaines caractéristiques des réseaux de neurones).
[^] # Re: Droit d'auteur et travailleurs
Posté par Moby-Dik . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
Heu, on se préoccupe peu du cas général. En informatique il n'y a que des applications spécifiques à un domaine donné. Le rendu 3D "cheap", les calculs de routage ont longtemps utilisé des tris en O(n) en limitant la dynamique des valeurs considérées (radix sort).
ce qui donne bien un temps minimal, il suffit de traduire ça en terme de cycle d'horloge.
Et la constante multiplicative, et le caractère asymptotique du O(n log n), ils sont partis où ? Ton estimation de cycles d'horloge, elle ne veut rien dire si elle se base sur la complexité théorique du problème et non sur la complexité pratique d'un algorithme...
Ouarf ! Je ne comprends pas ce que tu veux dire par technique.
Disons : procédés appliqués à un domaine précis pour obtenir des résultats précis, et mis au point par la maturation progressive d'un savoir-faire. Contrairement à la recherche scientifique où l'objectif est l'élargissement de l'horizon intellectuel et théorique, non la résolution de problèmes concrets et immédiats. Note que certaines disciplines peuvent se situer à la frontière entre les deux (exemple : des résultats mathématiques sont mis à profit pour s'assurer de certaines caractéristiques des réseaux de neurones).