Quelle est la complexité de la matrice plus?

J'ai trouvé certains mentionne dans une autre question de matrice plus d'être une équation du second degré de l'opération. Mais je pense que c'est linéaire.

Si je double la taille d'une matrice, j'ai besoin de calculer le double de la ajouts, pas de quadruple.

Les principales divergences de point de départ semble être quelle est la taille du problème. Pour moi, c'est le nombre d'éléments dans la matrice. D'autres pensent que c'est le nombre de colonnes ou de lignes, d'où le O(n^2) complexité.

Un autre problème que j'ai avec de la voir comme une équation du second degré de l'opération est que cela signifie que l'ajout de 3 dimensions des matrices est cubique, et l'ajout de 4-dimensions des matrices est O(n^4), etc, même si l'ensemble de ces problèmes peut être réduit au problème de l'ajout de deux vecteurs, ce qui a évidemment un linéaire de la solution.

Je suis bon ou mauvais? Si elle est mauvaise, pourquoi?

Êtes-vous en doublant le nombre total d'éléments dans la Matrice, ou chaque dimension de la Matrice?
Pourquoi le downvote? Cette question est pas claire ou pas utile?
bonne question 🙂

OriginalL'auteur R. Martinho Fernandes | 2009-12-08

  1. 7

    Comme vous l'a 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 de la largeur ou de la hauteur de la matrice. Qui est toujours correcte dépend en réalité de la problématique plus large de laquelle la matrice de plus fait partie.

    NB: sur certains matériels (GPU, les machines à vecteurs, etc) le plus peut courir plus vite que prévu (même si la complexité est toujours le même, voir la discussion ci-dessous), parce que le matériel peut effectuer des ajouts multiples en une seule étape. Pour un délimitée de la taille du problème (comme n < 3) il pourrait même être une seule étape.

    +1 Pour la mention de la matériel de parallélisation
    Le matériel ne change pas d'une complexité asymptotique. Il peut effectuer des ajouts à la fois, mais vous ne pouvez pas ajouter deux matrices avec moins d'ajouts que les éléments en eux. C'est une idée fausse très répandue, en particulier avec le multithreading. Le fait qu'il est plus rapide ne veut pas dire que c'est une complexité asymptotique est de moins en moins.
    C'est ce que je reçois par la pensée, trop dur, trop tard. Pourquoi ne pas les deux points de vue correct? Je me sens tellement stupide maintenant.
    vous êtes en droit de re complexité asymptotique, moi à la pensée trop tard 🙂 Peut-être que je peux m'en tirer en disant que si il existe une limite supérieure à la taille du problème, le matériel pourrait être en mesure d'ajouter un court-assez de colonnes de la matrice en O(1) fois
    oui, les constantes n'est pas considéré comme en grande-O notation; cependant, vous avez tendance à confondre le temps de la complexité avec le nombre-de-ops-complexité

    OriginalL'auteur akuhn

  2. 5

    Il est O(M*N) pour un 2-dimensions de la matrice à M lignes et N colonnes.

    Ou vous pouvez dire que c'est O(L) où L est le nombre total d'éléments.

    OriginalL'auteur rlbond

  3. 3

    Habituellement, le problème est défini à l'aide de matrices carrées "de taille N", ce qui signifie NxN. Par cette définition, la matrice de l'addition est un O(N^2) puisque vous devez visiter chacune des NxN éléments exactement une fois.

    Par cette même définition, la matrice de multiplication (en utilisant la place des matrices NxN) est O(N^3) parce que vous avez besoin pour visiter les N éléments dans chaque de la source de matrices pour calculer chacun des NxN éléments dans la matrice du produit.

    Généralement, toutes les opérations matricielles ont une limite inférieure de O(N^2) tout simplement parce que vous devez visiter chaque élément au moins une fois pour calculer tout ce qui concerne l'ensemble de la matrice.

    Toutes les opérations dans le dense, les matrices, les matrices creuses opérations sont délimitées par les non-zéro entrées.
    Touche...ce n'était pas de penser à sparse/bandes/sinon structuré matrices ici.

    OriginalL'auteur Drew Hall

  4. 2

    pense au cas général de mise en œuvre:

    for 1 : n
 for 1 : m
   c[i][j] = a[i][j] + b[i][j]

    si nous prenons un simple carré de la matrice, qui est n x n ajouts

    OriginalL'auteur µBio