En archi, on forme aussi des réseaux de tri qui font leur boulot en temps linéraire.
Ca ne change rien à la complexité algorithmique. Parler de temps d'exécution est un abus de langage quand on dit O(f(N)). O(f(N)) désigne le nombre d'opérations élémentaires nécessaire à la résolution du problème. Avec certaines architectures matérielles (parallélisme...) il est possible d'obtenir un "temps linéaire" alors que la complexité est quadratique. C'est un truc similaire qu'a utilisé DJ Bernstein pour essayer de démontrer qu'il sait diminuer la "complexité" de cassage du RSA (le fameux article qui fit du bruit il y a quelques mois...).
[^] # Re: Avancées technologiques du prochain Kernel
Posté par Moby-Dik . En réponse à la dépêche Avancées technologiques du prochain noyau Linux. Évalué à 3.
En archi, on forme aussi des réseaux de tri qui font leur boulot en temps linéraire.
Ca ne change rien à la complexité algorithmique. Parler de temps d'exécution est un abus de langage quand on dit O(f(N)). O(f(N)) désigne le nombre d'opérations élémentaires nécessaire à la résolution du problème. Avec certaines architectures matérielles (parallélisme...) il est possible d'obtenir un "temps linéaire" alors que la complexité est quadratique. C'est un truc similaire qu'a utilisé DJ Bernstein pour essayer de démontrer qu'il sait diminuer la "complexité" de cassage du RSA (le fameux article qui fit du bruit il y a quelques mois...).