En fait, qu'est ce qui est constant ?
La complexité de l'algo, ou l'évolution de sa complexité par rapport à sa charge (sa derivation quoi )???
Sa complexité rapportée à la taille des données. Si un algo est en O(N), cela veut dire que le nombre d'opérations nécessitées pour sa résolution est proportionnel à la taille des données traitées. Attention : on parle de pire cas ! Ainsi, un "tri rapide" est en O(N*N), bien que statistiquement les temps d'exécution soient plutôt proportionnels à N*log(N). Autre écueil : ne pas confondre "taille des données" (en bits) et "nombre de valeurs possibles".
La définition rigoureuse est (si je ne me trompe) :
Un algo est dit « de complexité O(f(N)) » si et seulement si :
il existe un entier M> 0, il existe un réel K> 0, tels que
pour tout entier N supérieur à M, pour tout jeu de données de taille N,
le nombre d'opérations nécessaire à l'exécution de l'algorithme est inférieur à K*f(N)
Il s'agit donc de pire cas asymptotique. Note : on parle de "résolution de problème" plutôt que d'"exécution d'algorithme" en général, sachant qu'on s'intéresse à un problème plus souvent qu'à un algorithme spécifique.
ou puis-je me renseigner pour comprendre ce jargon ?
Tu as intérêt à trouver un bouquin ou un cours de mathématiques appliquées, version débutant. Tu y trouveras toutes les bases de l'algorithmique et de la complexité des problèmes. Tu y feras également connaissance avec la célèbre machine de Turing, et ses éventuelles déclinaisons : machine de Turing avec oracle (non pas la base de données)...
[^] # 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é à 5.
La complexité de l'algo, ou l'évolution de sa complexité par rapport à sa charge (sa derivation quoi )???
Sa complexité rapportée à la taille des données. Si un algo est en O(N), cela veut dire que le nombre d'opérations nécessitées pour sa résolution est proportionnel à la taille des données traitées. Attention : on parle de pire cas ! Ainsi, un "tri rapide" est en O(N*N), bien que statistiquement les temps d'exécution soient plutôt proportionnels à N*log(N). Autre écueil : ne pas confondre "taille des données" (en bits) et "nombre de valeurs possibles".
La définition rigoureuse est (si je ne me trompe) :
Un algo est dit « de complexité O(f(N)) » si et seulement si :
il existe un entier M> 0, il existe un réel K> 0, tels que
pour tout entier N supérieur à M, pour tout jeu de données de taille N,
le nombre d'opérations nécessaire à l'exécution de l'algorithme est inférieur à K*f(N)
Il s'agit donc de pire cas asymptotique. Note : on parle de "résolution de problème" plutôt que d'"exécution d'algorithme" en général, sachant qu'on s'intéresse à un problème plus souvent qu'à un algorithme spécifique.
ou puis-je me renseigner pour comprendre ce jargon ?
Tu as intérêt à trouver un bouquin ou un cours de mathématiques appliquées, version débutant. Tu y trouveras toutes les bases de l'algorithmique et de la complexité des problèmes. Tu y feras également connaissance avec la célèbre machine de Turing, et ses éventuelles déclinaisons : machine de Turing avec oracle (non pas la base de données)...