4 Réponses :
Comme vous l'avez déjà noté, cela dépend de votre définition de la taille du problème: est-ce le nombre total d'éléments, ou la largeur / hauteur de la matrice. Lequel est correct dépend effectivement du problème plus large que l'addition matricielle fait partie.
NB: sur du matériel (GPU, des machines vectorielles, etc.) L'addition peut fonctionner plus rapidement que prévu (même si la complexité est toujours la même, voir la discussion ci-dessous), car le matériel peut effectuer plusieurs ajouts en une seule étape. . Pour une taille de problème délimitée (comme n <3), elle pourrait même être une étape.
Le matériel ne changera pas la complexité asymptotique. Il peut effectuer plus d'ajouts à la fois, mais vous ne pouvez pas ajouter deux matrices avec moins d'ajouts que les éléments d'eux. C'est une idée fausse commune, surtout avec la multithreading. Le fait que c'est plus rapide ne signifie pas que sa complexité asymptotique est moins.
C'est ce que je reçois en pensant trop fort trop tard. Pourquoi les deux points de vue ne pouvaient-ils pas être corrects? Je me sens si muet maintenant.
@martinho Vous avez raison de faire une complexité asymptotique, je pense trop tard :) Peut-être que je peux vous échapper de dire que s'il y a une limite supérieure à la taille du problème, le matériel pourrait être capable d'ajouter des colonnes matricielles suffisantes dans O ( Une fois
Je pense que la logique est une sorte de triche.
@Adrian: Qu'est-ce que Rlbond a dit. Vous n'avez toujours pas réduit le nombre d'ajouts. S'il vous plaît n'impliquez pas de matériel sur des sujets théoriques.
En plus de cette réponse (très bonne), considérez que si les données calculées dépassent la taille du cache de mémoire, vous allez avoir un mauvais moment.
Je suis prêt à accepter cette réponse quand elle cesse de réclamer que vous pouvez réduire la complexité avec du matériel. Arrête ça! Oui, vous pouvez le rendre plus rapide, mais c'est toujours O (n) ou O (n ^ 2). Plus rapide o (n) est O (n). O (n / 2) = O (n). en.wikipedia.org/wiki/big_o_notation
En fait, avec la parallélisation HW, vous pouvez réduire la complexité de temps puisque vous effectuez deux ajout ou plus par unité de temps; Le nombre total d'addition ne change pas cependant
Oui, les constantes ne sont pas considérées dans la notation Big-O; Cependant, vous avez tendance à confondre la complexité du temps avec la complexité numérique de l'OPS
C'est O (m * n) pour une matrice à 2 dimensions avec M lignes et n colonnes.
ou vous pouvez dire que c'est O (l) où L est le nombre total d'éléments.
Pensez à l'affaire General Mise en œuvre:
for 1 : n for 1 : m c[i][j] = a[i][j] + b[i][j]
Habituellement, le problème est défini en utilisant des matrices carrées "de taille n", ce qui signifie nxn. Par cette définition, la matrice addition est une O (n ^ 2) puisque vous devez visiter chacun des éléments NXN exactement une fois.
Par cette même définition, la multiplication de matrice (utilisation de matrices carrées NXN) est O (n ^ 3) car vous devez visiter N éléments dans chacune des matrices source pour calculer chacun des éléments NXN dans la matrice de produit.
En règle générale, toutes les opérations matricielles ont une limite inférieure de O (n ^ 2) simplement parce que vous devez visiter chaque élément au moins une fois pour calculer tout ce qui implique la matrice entière.
Toutes les opérations dans matrices denses , les opérations de matrice clairsemées sont délimitées par les entrées non nulles.
@Adrian: Touche ... ne pensait pas à des matrices raffinées / bandées / structurées autrement ici.
Doublez-vous le nombre total d'éléments dans la matrice ou chaque dimension de la matrice?
Pourquoi le bowvote? Cette question n'est-elle pas claire ou non utile?