Discussion :

[abidineb]

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.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
for i=1 to n 
F(i)=A*Z(i)
end
 
for i=1 to n 
ww(i) = (Q'*F(i))
end
 
for i=1 to 50
F(i)=A*Z(1)+i
end

Je n'ai aucune base dans l'algorithmique, si qql peut m'aider a faire le calcul de la complexite temporelle O(...).
Merci d'avance.
Cordialement

[abidineb]

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

[pseudocode]

F(i)=A*Z(i), avec dim(A)=m*n, et dim(Z(i))=n.

Tu multiplies deux tableaux de dimensions différentes ? ?

[abidineb]

Re
Oui une matrice de dimension m*n et l'autre n*1, résultat obtenu: m*1.

C'est juste non.

Merci

[abidineb]

c'est a dire le vecteur F(i) sera de dimension m*1.

[abidineb]

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

[Vakhyw]

Bonsoir

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
for i=1 to n 
F(i)=A*Z(i)
end
 
for i=1 to n 
ww(i) = (Q'*F(i))
end
 
for i=1 to 50
F(i)=A*Z(1)+i
end

l2 : O(m*n) (n multiplications + n additions pour chacune des m lignes)

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

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).

[abidineb]

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???????????

[abidineb]

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??

[abidineb]

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.

[pseudocode]

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???????????

Uniquement en cas de complexité asymptotique, c'est à dire la notation O(...).

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.

[abidineb]

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.
Cordialement

[pseudocode]

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.
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, ...).

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".

[abidineb]

Bonjour
Vous dites 2eme cas, c'est a dire Temps=O(m*n*n), cette écriture donc est tout a fait juste??????????

Cordialement

[pseudocode]

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.

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²".

[abidineb]

Merci pour vos réponses, je continue a travailler sur cette notion necessaire.
Cordialement

[Franck Dernoncourt]

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).

[abidineb]

Merci beaucoup, je vais lire ça. j'en ai vraiment besoin.
Cordialement