Version imprimable
Bonsoir
J'essaye d’étudier la complexite de cet algorithme cité en dessous:
Avec: dim(A)=m*n, et dim(Z(i))=n*1, dim(Q)=m*1.
Je n'ai aucune base dans l'algorithmique, si qql peut m'aider a faire le calcul de la complexite temporelle O(...).Code:
2
3
4
5
6
7
8
9
10
11
Merci d'avance.
Cordialement
Bonjour a tous
L'algorithme est peut être un peu complexe. Juste pour éclaircir c'est quoi dim, c'est tout simplement la dimension.
Merci
Cordialement
Tu multiplies deux tableaux de dimensions différentes ? :koi: ?Citation:
F(i)=A*Z(i), avec dim(A)=m*n, et dim(Z(i))=n.
Re
Oui une matrice de dimension m*n et l'autre n*1, résultat obtenu: m*1.
C'est juste non.
Merci
c'est a dire le vecteur F(i) sera de dimension m*1.
Bonsoir
Dites moi juste est ce qu'il n'est pas compréhensible afin que je puisse l’éclaircir encore, ou s'il n' y a pas une solution pour avoir la complexite de algorithme.
Merci
l2 : O(m*n) (n multiplications + n additions pour chacune des m lignes)Citation:
Envoyé par abidineb
l1-3 : O(m*n*n) (n * complexité de l2)
l6 : O(m) (m multiplications + m additions)
l5-7 : O(n*m) (n * complexité de l6)
l10 : O(m*n) (complexité de l2)
l9-11 : 50 * O(m*n) = O(m*n) (multiplication par une constante ...)
au total : O(m*n*n) (en fait la complexité de l1-l3, qui est la plus grande de tout l'algo)
Voila voila :ccool:
Après en l10 ça sert à rien de calculer 50 fois A*Z(1). A moins qu'il ne s'agisse d'une faute et que tu voulais écrire A*Z(i). (Ce qui ne change pas la complexité de l'algo).
Salut
Merci beaucoup pour votre réponse tout a fait logique donc c'est O(m*n*n), donc dans le calcul d'une complexite algorithmique, faut négliger les plus faibles???? est ce que c'est juste???????????
Par exemple si on ajoute cette partie a notre code après la ligne11:
for i=1 to n
ww(i) = (Q'*F(i))
end
Donc la complexite reste inchangée??
Est ce que c'est juste??
Je pose juste ces questions pour clore cette discussion, parce que je n'ai pas saisi comment peut on négliger les autres complexités devant O(mnn) sans connaitre les valeurs de n et m, je vais les fournir:
n=16;
m=50000
Merci encore une fois.:ccool:
Uniquement en cas de complexité asymptotique, c'est à dire la notation O(...).Citation:
Envoyé par abidineb
Cette complexité permet d'estimer le comportement asymptotique de l'algorithme (en terme de nombre d'opérations) en fonction de la TAILLE des données en entrée.
Bonsoir
Je commence a bien cerner les choses. merci
Donc c'est uniquement en cas de complexité asymptotique.
Donc est ce que c'est juste de mettre temps=-m*n*n
( =- je veut dire approximativement) sachant que temps est en seconde et m, n sont des constantes.????????? donc pas les mêmes unités????
C'est vous me répondez a cette question, j'aurai saisi tout.
Merci encore une fois.:ccool:
Cordialement
Pour les algorithmes, on parle habituellement en terme de "nombre d'opérations" et pas en "seconde". En effet, le temps en seconde dépend de l'implémentation (langage, ...) et du matériel (cpu, ...).Citation:
Envoyé par abidineb
Ceci mis à part, tu peux dire au choix que :
- cet algorithme nécessite d'exécuter environ m*n² opérations
- cet algorithme a une complexité de O(m*n²)
NB: dans le 2ème cas, ce n'est pas du "environ" mais du "exactement".
Bonjour
Vous dites 2eme cas, c'est a dire Temps=O(m*n*n), cette écriture donc est tout a fait juste??????????
Cordialement
Hum, plus ou moins.Citation:
Envoyé par abidineb
Le signe "=" n'a de signification mathématique que si on parle de fonctions :
Temps(m,n) = O(m*n*n)
Cette notation signifie que la fonction "Temps(m,n)" se comporte asymptotiquement comme la fonction "m*n²".
Merci pour vos réponses, je continue a travailler sur cette notion necessaire:ccool:.
Cordialement
Les algorithmes dont la complexité et la plus difficile à calculer sont ceux présentant des appels récursifs. Les autres sont normalement facile à calculer si l'on maîtrise correctement la big O notation : http://en.wikipedia.org/wiki/Big_O_notation
Pour mieux comprendre la complexite des algorithmes récursifs, je conseille de lire les chapitres 4 et 5 (si mes souvenirs sont bons) intitulé "Recurrences" et "Probabilistic Analysis and Randomized Analysis" du livre de référence http://algo.developpez.com/livres/#L2100039229
EDIT : petite précision, j'ai lu très rapidement le thread mais il faut bien distinguer complexité spatiale (mémoire requise) et complexité temporelle (nombre d'opérations). D'ailleurs il faut souvent trouver un compromis entre les deux -> space-time tradeoff (http://en.wikipedia.org/wiki/Space-time_tradeoff).
Merci beaucoup, je vais lire ça. j'en ai vraiment besoin.
Cordialement