Ben en fait en informatique théorique, on se pose la question de tout codeur: comment mesurer le 'temps' que met un programme pour faire une opération donnée, en fonction de la taille de l'entrée ?
Le but du jeu, c'est d'obtenir une 'mesure théorique' du temps d'un aglo qui ne dépend pas d'un ordi ou d'une mesure réelle (c'est pas contre les benchmarks réels, mais y'a bcp de raison qui font que c'est intéressant et complémentaire )
Comme ça si t'as deux algo qui font la même chose, (genre deux programme qui trient une liste ), on est capable de dire, juste à lire le (pseudo-)code, qui est le plus rapide, et qui utilise le plus de mémoire (même principe de la mesure)
Pour ça, on fixe en général une 'unité de calcul': si on voudrait être très précis ça pourrait être le nombre de cycles nécessaire à tel processeur, mais bon comme on est pas suicidaire on dit en général qu'une opération 'simple' (affectation, addition, multiplication, comparaison, ..) se fait en un temps de 'une unité de calcul' (c'est imagé )
Après, si je fais le programme de tri suivant:
dim(L1)->N
Pour i de 1 à N
Pour j de 1 à N-1
Si L1(j) > L1(j+1) alors
L1(j) -> A
L1(j+1) -> L1(j)
A -> L1(j+1)
FinSi
FinPour
FinPouron cherche à compter le nombre d'opération 'élémentaires' que fait le programme en fonction de la taille de la liste à trier, N
Si on compte méticuleusement:
1 opération pour l'affectation de N
N * (N-1) * (1 [comparaison] + (0 ou 3) [affections dans le cas du si] )
bref, si la liste est déjà triée, on fait jamais le bloc du 'si' et on va faire 1+N*(N-1) opérations
Dans les autres cas, au 'pire du pire' on aurait toujours le bloc du 'si' à faire, et donc on fait moins de 1+N*(N-1)*4
Bon, quand N devient grand, c'est un peu ridicule de compter le '+1', et N*(N-1) ~ N² pour N->infiny, on dit donc que le programme est en 4*N², voir O(N²) [on 'néglige' le facteur devant, ça donne un truc plus grossier mais plus simple. )
Maintenant si tu fais un programme de tri plus intelligent, (par exemple, le tri-rapide), on peut voir que la complexité en temps est de l'ordre de N*log(N)
Quand N est très grand, qu'importe les constantes devant, cste1*N.log(N) << cste2*N², donc on peut dire que le programme deux est plus rapide que le 1.
Bon après c'est une question de précision, on garde la constante numérique devant quand on veut faire des comparaisons précises, genre tu peux dire 'mon prog fait le truc en 9*N au lieu de 11*N donc il est meilleur', etc.
C'est assez corrélé à la réalité, pourvu qu'on fasse pas trop d'hypothèses dégueulasses, que le taille des entrées soit assez grande, que les deux progs soient 'aussi bien' codés (Par exemple si N=2, le fait de 'dégager' les +1 etc fait que bon celui censé être le plus lent peut en fait être le plus rapide)
Pour revenir à notre cas, comme N<100 (les listes ti-basic c'est limité à 99 ? ), et que les fonctions built-in sont parfois vraiment plus rapides que les mêmes faites à la main, ça donne qu'une idée très vague du truc qui sera le plus performant pour de vrai. Sauf si l'écart est super grand genre y'a un prog en 2*N et l'autre en exp(N), là dès que N dépassera 10 tu verra bien l'écart..
edit: français, pre
isp A
ortD(L1
(mais tu peux toi aussi l'éditer)
)