pourquoi est l'heure de la complexité de la place de la multiplication de matrice définie comme O(n^3)?

Je suis venu dans ce dans de multiples sources (en ligne et les livres) - temps de marche de la place de la multiplication de matrice est O(n^3) pour les matrices de taille nXn. (exemple - algorithme de multiplication de matrice de temps de la complexité)

Cette déclaration semble indiquer que la limite supérieure de la durée de fonctionnement de ce processus de multiplication est C. n^3 où C est une constante et n>n0 où n0 est une entrée au-delà de laquelle cette limite supérieure est vrai. (http://en.wikipedia.org/wiki/Big_O_notation et Quelle est la différence entre Θ(n) et O(n)?)
Le problème est que je n'arrive pas à tirer les valeurs des constantes C et n0.

Mes questions -

  1. Quelqu'un peut-il fournir une preuve mathématique de l'instruction " big Oh, square de la multiplication de matrice est O(n^3)' ?
  2. quelles sont les valeurs de C et n0 ?
Pour chaque cellule (n^2), vous allez par le biais de n cellules dans les lignes et les colonnes et les multiplier ensemble, il est donc O(n^3).
donc, si nous disposons de 2 matrices A et B est nXn. et leur produit est la matrice X de taille nXn. vous êtes ce qui implique que pour chaque valeur de X (il y a n^2 valeurs dans X), vous devez parcourir un total de n d'éléments de A et de B ? ou est-ce plus comme la n d'éléments de A et de n éléments dans B, ce qui rendrait ce n^4 et pas n^3.
n d'éléments de A et de n éléments dans B, oui, mais il s'élève à 2n, pas n^2. De sorte que le résultat final est O(n^3).

OriginalL'auteur Quest Monger | 2012-11-22

  1. 5

    1. Il y a 3 pour les boucles les unes dans les autres allant de 0 à n-1 (ou de 1 à n) chacune (comme on peut le voir dans le lien que vous avez fourni, même si ce n'est pas tout à fait correct), il en résulte en O(n3). Formaliser dans une bonne preuve devrait être assez facile.

    2. a) Pour une preuve formelle, la durée doit être définie en termes d'une série d'opérations, souvent pris à toute opération arithmétique. À l'intérieur de l'3 pour les boucles il y a 2 opérations arithmétiques (1 multiplication, 1), ainsi, nous obtenons 2.n3, donc C = 2.

      b) n0 = 0, car cela est vrai à partir de n = 1

    Noter que, depuis le big-O est juste une limite supérieure, on peut aussi dire de la complexité de cet algorithme est O(nk) pour tout k >= 3 (même ne serait pas vrai si nous utilisons de grandes-Thêta de notation). Nous pouvons également prendre en C et n0 pour une valeur supérieure à 2 et 0, respectivement (étant donné que l'exigence n'est pas de trouver la plus petite valeur possible).

    merci! et merci pour la correction de mon erreur, je voulais dire une asymptotique de la limite supérieure. désolé pour la confusion. pertinentes - mathforum.org/library/drmath/view/51904.html
    merci beaucoup pour le mathforum lien... c'était le plus facile à comprendre de la réponse, je n'ai pas encore rencontré!

    OriginalL'auteur Dukeling