Version imprimable
Bonjour à tous,
SVP J'ai deux algorithmes et il faut que je compare leur complexité en terme de nombre de flops ? J'ai jamais vu ou entendu parler de ça, j'ai essayé de voir sur google mais j'arrive pas à trouver de la Doc, SVP pouvez-vous me conseiller des références la-dessus ou me donner des liens?
Merci bcp et bonne journée...
Moi j'ai tapé "flops" dans google et la première réponse était pertinente.
C'est pas très compliqué, qu'est-ce que tu ne comprends pas ?
Merci bcp ...
Bjr a tous,
Désolé, j'ai cru comprendre, mais j'ai pas vraiment compris comment on calcul le grand O des folps -O(...)- ...
SVP voici un petit exemple sur matlab qui m'aidera énormément ,,,
Où il faut calculer le nombre de flops de chaque instruction et le nombre de flops totale
%
[U,V,D]=svd(X*X');
En=U(:,Ns+1:end);
En2=En*En';
W=sort(X);
[I,J]=min(X);
%MMMMMMMMMMMerci bcp
tu confonds...
- O(N) est un calcul de complexité d'un algorithme
- Un Flop est une mesure de la vitesse de calcul d'un processeur en précision flottante
Rien à voir
Merci pour cette précision,
donc pouvez-vous SVP me dire comment je peux calculer la compléxité de cet algorithme, car je suis sur via un exemple je pourrai comprendre mieux
Merci encore
Salut !
Est-ce que ce concept a un sens, étant donné queCitation:
complexité en terme de nombre de flops
- les diverses opérations en virgule flottante ne prennent pas le même temps;
- les rapports des temps de calcul ne sont pas le mêmes en REAL*4 et en REAL*8;
- les fonctions transcendantes disponibles sur les processeurs modernes devraient être prises en compte;
- les transferts entre registres, cache, RAM contribuent de manière non négligeable au temps de calcul
Jean-Marc Blanc
Bjr à tous, et merci encore...
Voila j'ai changé le titre, et j'avais écris ça en me basant sur le livre de GOLUB '' Matrix computations '' qui définie le flop en terme de nombre de multiplication et d'addition...
Mais bon, le problème n'est pas sur la signification du flop, je veux seulement calculer la complexité de ce petit algorithme, en trouvant le grand O(...) totale, je vous remercie infiniment ...
[U,V,D]=svd(X*X');
En=U(:,Ns+1:end);
En2=En*En';
W=sort(X);
[I,J]=min(X);
Salut !
Outre les approches théoriques du problème, sur lesquelles plusieurs collègues te renseigneront bien mieux que moi, tu peux envisager une approche "expérimentale": Soit n la taille de X. Tu réécris ton programme en ne mettant qu'une opération élémentaire par instruction, et tu prévois un compteur as pour les additions/soustractions et un compteur md pour les multiplications/divisions. Tu passes ce programme pour diverses valeurs de n, puis tu décomposes les fonctions as(n) et md(n) en séries de Mac-Laurin. Un problème peut provenir du fait que la fonction svd calcule n racines carrées.
Jean-Marc Blanc
Merci a tous,
A vrai dire, j'ai jamais fais de l'algorithmique ou quelque chose du genre (MALHEUREUSEMENT :( ), et je ne sais pas comment faire un compteur spécialement pour les additions ou pour les multiplication ? y'a-t-il une fonction prédéfinie dans matlab?
Cependant , si on considére O(n) comme représentant n addition et n multiplication, serai-t-il correct de faire ça :
%====Si X est de taille 1xN et En de taille NxM (M=end-Ns)
[U,V,D]=svd(X*X'); %===O((Nx1)²)
En=U(:,Ns+1:end); %===O(1)
En2=En*En'; %===O(NxM)
W=sort(X); %===O(1)
[I,J]=min(X); %===O(N)
Est l'ordre total sera O(N²+NxM) ?
MERCI BCP POUR VOTRE AIDE
Bonjour,
Tu demandes de l'aide pour calculer la complexité d'un algo, mais le problème c'est que tu nous donnes ton algo dans un langage que personnellement je ne comprends pas...
Tu pourrais le réécrire en pseudocode ?
Que veut dire svd, U(:,....) etc...Code:
2
3
4
5
6
C'est vrai, j'ai pas détaillé les instructions, car ce sont des fonctions prédéfinies dans Matlab :
%====Si X est de taille 1xN et En de taille NxM (M=end-Ns)
[U,V,D]=svd(X*X'); %Singular value decomposition
En=U(:,Ns+1:end); %En sera constitué de toutes les lignes de U mais que des colonnes partant de Ns+1 jusqu'à la fin
En2=En*En'; % Multiplication matricielle entre En et sa trans-conjugée
W=sort(X); % Réarrangement croissant du vecteur X
[I,J]=min(X); % recherche du minimum de X où I est la valeur et J l'indice
Ce que je propose et je souhaiterai voir si c'est juste :
NB:j'ai pas le code source de la 'svd' mais on suppose qu'elle est équivalente à O((Nx1)²) (Car le but pour moi j'ai de comprendre surtout la logique du calcul de l'ordre total)
[U,V,D]=svd(X*X'); %===O((Nx1)²)
En=U(:,Ns+1:end); %===O(1)
En2=En*En'; %===O(NxM)
W=sort(X); %===O(1)
[I,J]=min(X); %===O(N)
Est l'ordre total sera O(N²+NxM) ?
MERCI BCP POUR VOTRE AIDE
Vu que tu n'as pas de boucle, pour calculer la complexité ( O ) il faut calculer la complexité de chaque opération et prendre la plus couteuse.Citation:
Envoyé par shinobida
Si ce que tu as écrit est juste (mais j'en doute) alors la complexité serait en O(N²) ou O(N*M) selon si N > M ou pas.
Pour la complexité de chaque opération :
Déjà j'ai un doute sur le fait que ton sort soit en O(1).
voir http://fr.wikipedia.org/wiki/M%C3%A9thode_de_tri : on ne connait pas mieux que O(n * log n)
Comme on a pas le détail de l'algo je ne sait pas si c'est justeCitation:
[U,V,D]=svd(X*X'); %Singular value decomposition
En=U(:,Ns+1:end); %En sera constitué de toutes les lignes de U mais que des colonnes partant de Ns+1 jusqu'à la fin
Pour le calcul de En2, comment tu obtiens En' ?
Merci BCP, votre aide est inestimable
Voila, donc vous aviez raison, je me suis trompé, j'ai fais une recherche et enfin j'ai trouvé la complexité de la SVD ( thése : http://www.laas.fr/~henrion/papers/phd_zuniga.pdf) pour une matrice m*n y'a 4m²n+8n²m+9n^3.
Donc pour le même exemple, en corrigeant les erreurs (j'espère que cette fois c'est juste) et en ajoutant une boucle :
%====Si X est de taille Nx1 et En de taille NxM (M=end-Ns)
For t=1:T
[U,V,D]=svd(X*X'); %===O(N²)
En=U(:,Ns+1:end); %===O(1): car matlab fait juste des affectations dans une nouvelles matrice En (M affectation de matrice colonnes, et zéro opération addition et multiplication)
En2=En*En'; %===O(NxM) (pour le En' c'est aussi des affectation du genre pour tout i,j on En'(i,j)=En(j,i)
W=sort(X); %===O(N.logN) comme vous me l'aviez dit
[I,J]=min(X); %===O(N)
End
Sachant que N>M, dans ce cas serait-il juste de dire que la complexité totale = O(T*N²) ?
MMMMMMMMMMMMMMMMERCI BCP POUR TOUT VOTRE AIDE :yaisse2:
For t=1:T
[U,V,D]=svd(X*X'); %===O(N²)
Je croyais que c'était 4m²n+8n²m+9n^3 ?
Dans ce cas ça ferait plutot N^3
En=U(:,Ns+1:end); %===O(1): car matlab fait juste des affectations dans une nouvelles matrice En (M affectation de matrice colonnes, et zéro opération addition et multiplication)
Une affectation peut être vu comme une opération il me semble
En2=En*En'; %===O(NxM) (pour le En' c'est aussi des affectation du genre pour tout i,j on En'(i,j)=En(j,i)
W=sort(X); %===O(N.logN) comme vous me l'aviez dit
[I,J]=min(X); %===O(N)
End
Pour la complexité totale, dans la cas d'une boucle de 1 à T, multiplier la pire des opération en complexité par le nombre de boucle (T) est correct.
Merci pour votre réponse :
Pour la SVD, pour une matrice m*n y'a 4m²n+8n²m+9n^3, comme notre X est de dimension N*1 donc on aura O(N²), (désolé, les notations que j'ai choisi prêt à confusion).
J'ai cru lire dans un site (http://removers.free.fr/spip/article.php?id_article=75) qu'il fallait calculer la complexité d'affectation toute seule et la complexité dû au addition et au multiplication toute seule ? Est-ce la bonne méthode et comment on peut quantifier une opération d'affectation par rapport à une addition ou une soustraction? Peut-on le faire en calculant le temps mis par le langage de programmation d'effectuer une seule addition et une seule affectation et prendre la complexité dû à l'instruction la plus longue en terme de temps?