Discussion :

[ssi_nadia]

Bonjour,
Je bloque avec un exercice, je ne sais même pas comment je dois procéder pour le résoudre, s'il vous plait s'il y a quelqu'un qui peut me donner une idée juste pour commencer.
voici l'énoncé:
Supposons qu'on ait écrit une procédure pour additionner m matrices carrées de n*n.Si l'addition de deux matrices carrées nécessite un temps d'exécution de O(n²) quelle sera la complexité de cette procédure en fonction de m et n ?

Merci d'anvance

[kwariz]

Bonsoir,

peux-tu esquisser un algorithme qui additionne m matrices ? combien d'addition de matrices effectues-tu ?

[sologne]

Bonjour,

lorsque tu additionnes deux matrices carrées tu réalises :

Code :

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

1
2
3
4
5
6
 
Pour i allant de 1 à N faire
   Pour j allant de 1 à N faire
      Cij = Aij+Bij
   Fin Pour
Fin Pour

C'est imbrication des deux boucles Pour qui nous conduit à l'ordre N^2.

lorsque tu vas additionner m matrices tu ne feras que appeller (m-1) ta procédure d'addition de deux matrices.

Donc l'ordre de grandeurs des calculs augmenta proportionnellement aux nombre de matrices. d'ou un ordre = (m-1)*N^2