bonjours à tous .mon exercice set le suivant: ecrire un algorithme qui recherche parmis 3 nombres le plus petits.en fait l'algorithme est un programme qu'on veut integrer dans une machine.
bonjour
a, b, c les 3 nombres
X désigne comme le plus petit
début
X=a
Si X>b alors X=b
Si X>c alors X=c
fin
Y'a sûrement plus simple et plus structuré
Philoux
"Y'a sûrement plus simple et plus structuré"
non, je pense que la on aproche de la perfection ! (en tous cas en nombre d'operation a executé on peut pas faire mieux je pense )
bonjour
comment est définie la complexité d'un algorithme ?
nombre d'opérations, natures des opérations, nombre de lignes, nombre de variables, routines/subroutines... ?
Philoux
En fait, c'est assez difficile à définir.
Disons que c'est le nombre d'opérations élémentaires (que ce soit une opération arithmétique, une comparaison, un accès à une source externe)...
généralement, on se concentre sur une ou deux opérations précises (celles qui sont "intéressantes")
Par exemple, dans un algo de tri, tu t'intéresse au nombre de comparaison effectuées.
merci
celà dépend-t-il du processeur ? du langage ? de la structure des données ?
Philoux
pour le temps de calcul oui, mais le calcul de la complexité ne doit pas faire intervenir la vitesse du processeur, le langage,...
L'utilité de la théorie de la complexité est de comparer des algos qui sont sensés faire la même chose sur les mêmes données. Elle doit donc s'affranchir de toutes source de "perturbation" externe..
sa depend de quoi on parle en fait... on compte ce qu'on apelle une operation elementaires... mais "l'operation elementaire" n'est pas toujour tres bien definit... (et de toute facon un temps de calcule est toujour sous la forme d'un O(g(n)), j'aimmais de valeur precise)
par exemple l'exponentiation modulair pour le calcule de x^n est en O(lg n) si on travaille sur une representation des nombres a p bit fixé, en O(lg x * n^2) si on travaille sur un entier x "long" alors que a la base, c'est exactement le meme algo
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :