Vitesse d'un algorithme

[Evil.Saien]

Bonjour,
je suis pas informaticien de formation, pourtant je suis en train de programmer des algo dont j'aimerais connaitre la vitesse.
Comment est-ce qu'on fait ?
Par exemple, pour une simple boucle for (int i=0; i<max; i++) je me doute que la vitesse et en fonction de max de manière linéaire, noté il me semble, O(N).
Mais lorsque ca se complique, je sais pas trop comment faire.
De plus si on utilise plusieurs algorithme a la suite, par exemple une FFT O(N^2logN) et une boucle O(N), quelle devient la vitesse ??

Merci
++
-----

[invite36602837]

Ben moi, je suis informaticien de formation et je ne connais pas la formule pour calculer exactement la vitesse (d'ailleurs si qqun la connais, je suis preneur). Je me base plutot sur le nombre d'instruction a executé (sachant qu'une boucle est une suite a prendre en compte, genre NbLigne*NbBoucle = nombre de cycle CPU). Un CPU execute une instruction a la fois (une ligne peut contenir plusieurs instruction), donc moi je decompose le code en ligne simple (1 ligne = 1 instruction), je calcul le nombre de cycle et je compare la frequence de mon CPU avec le nombre de cycle pour avoir le temps d'execution, pour une fonction par exemple. Mais si tu es sur un environnement multitache, tu doit prendre en compte le fait que ton applic n'est pas constamment executé, donc la vitesse depend des instructions a executé, mais aussi des autres applic qui tourne. Se qui forcement diminue le temps CPU disponible pour toi.

[invitea0046ad4]

salut

en complément à ce que dit uinet (tout à fait exact) :

Tout dépend de l'application.
S'il s'agit d'un programme pour un micro-controleur pilotant un système temps réel, on peut effectivement avoir besoin de connaitre le temps d'exécution à la µs près, et il faut dans ce cas compter proprement les instructions.
Pour une application scientifique écrite dans un langage de plus haut niveau, on s'intéresse plutôt au comportement asymptotique des algorithmes : le fait de savoir qu'un algorithme a une complexité en O(N) ou O(N.log(N)).
Mathématiquement O(N)+O(N.log(N)=O(N.log(N)) si les deux
algorithmes s'exécutent consécutivement (ne sont pas imbriqués).
La détermination de la complexité d'un algorithme est en général un problème difficile.
Bon, c'est la théorie.
En pratique, la constante de proportionnalité est aussi importante, et quand on ne connait pas le détail de tous les processus qui s'exécutent simultanément, le mieux est de faire quelques mesures, ce qui permet d'écrire explicitement une formule du type T = K0 + K1.N + K2.N*log(N).
Plus qu'à faire quelques mesures pour déterminer K0, K1, K2.

A+

[Evil.Saien]

Salut,
pour etre plus précis, il ne sagit pas de la vitesse de l'algorithme, mais de sa compléxité (le mot m'avait échappé de la bouche).
Donc les instructions simples a l'intérieur des boucles ne sont pas a prendre en compte. Ce que je doit trouver, c'est plutot le nombre de boucle que je fais en fonction de la taille du signal...

[A voir en vidéo sur Futura]

[invitea0046ad4]

Alors il faut bien faire une analyse mathématique.
Pour la FFT 1D, la complexité est N.log(N), ce qui se démontre en analysant l'algorithme (démo par récurrence il me semble).

A+

[acx01b]

ça dépend énormément du language où tu programmes....

si tu programmes en assembleur tu vas pouvoir exactement calculer sans executer ton programme le temps qu'il va mettre...
si c'est en c, tu vas devoir le faire par la pratique, en comparant diverses valeurs que tu auras mesuré...

[invitedebe236f]

tu as la fonction elle retourne les milliseconde depuis l ouverture de windows soit par 1 soit par 16
Public Declare Function timeGetTime Lib "winmm.dll" () As Long

ces 2 fonctions serve a passer de 1 a 16 milliseconde mais bon ca marche pas toujours
Public Declare Function timeBeginPeriod Lib "winmm.dll" (ByVal uPeriod As Long) As Long
Public Declare Function timeEndPeriod Lib "winmm.dll" (ByVal uPeriod As Long) As Long

tu ne peux pas comparer une fft et une simple boucle
une fft c est tous un algo qui comporte n boucle imbriquer ou pas
tu choisi le fft parce que c est rapide apres tu l ecrit comme tu veux en essayant de diminuer les boucles

j ai ecrit une fft en vb et je suis en train de l ammeliorer pour aller plus vite pour l instant 3*1048576 de chiffre en 5s sur un amd 1.3 ghz

[invitedebe236f]

Salut,
pour etre plus précis, il ne sagit pas de la vitesse de l'algorithme, mais de sa compléxité (le mot m'avait échappé de la bouche).
Donc les instructions simples a l'intérieur des boucles ne sont pas a prendre en compte. Ce que je doit trouver, c'est plutot le nombre de boucle que je fais en fonction de la taille du signal...

il me semble

nbmulti = Log(nbchiffre) / Log(2)
nbadd = nbmulti + 1
donc si tu prend 1048576 valeur faut faire 21 x la boucle d addition
pour les 1048576 valeur
et 20 x boucle de multi en sachant que tu ne multiplie jamais tous les 1048576 a chaque fois