algorithme de multiplication matricielle complexité temporelle

Je suis venu avec cet algorithme de multiplication de matrice. J'ai lu quelque part que la multiplication de matrice a une complexité temporelle en o(n^2).
Mais je pense que mon cet algorithme donnera o(n^3).
Je ne sais pas comment calculer le délai de la complexité de boucles imbriquées. Donc merci de me corriger.

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]

source d'informationauteur zedai

  1. 13

    Les naïfs algorithme, qui est ce que vous avez une fois que vous corriger comme indiqué dans les commentaires, est O(n^3).

    Il existe des algorithmes qui permettent de réduire un peu cela, mais vous n'êtes pas susceptibles de trouver un O(n^2) mise en œuvre. Je crois que la question de la plus efficace de la mise en œuvre est encore ouverte.

    Voir cet article de wikipédia sur La Multiplication De Matrice pour plus d'informations.

  2. 34

    À l'aide de l'algèbre linéaire, il existe des algorithmes qui permettent d'atteindre une meilleure complexité que le naïf O(n3). Solvay Strassen algorithme permet d'obtenir une complexité de O(n2.807) en réduisant le nombre de multiplications nécessaires pour chaque 2x2 sous-matrice de 8 à 7.

    Le plus rapide algorithme de multiplication de matrice est Chaudronnerie-Winograd algorithme avec une complexité de O(n2.3737). Sauf si la matrice est énorme, ces algorithmes ne pas entraîner une grande différence dans le temps de calcul. Dans la pratique, il est plus facile et plus rapide d'utiliser des algorithmes parallèles pour la multiplication matricielle.

  3. 9

    La manière standard de la multiplication d'un m-par-n de la matrice par un n par p la matrice a une complexité O(mnp). Si tous ceux qui sont "n" pour vous, c'est O(n^3), pas de O(n^2). EDIT: il ne sera pas en O(n^2) dans le cas général. Mais il existe des algorithmes plus rapides pour certains types de matrices -- si vous en savez plus, vous pourriez être en mesure de faire mieux.

  4. -1

    Dans la multiplication de matrice il y a 3 pour la boucle, nous utilisons depuis l'exécution de chaque boucle requiert du temps, de la complexité O(n). Donc, pour les trois boucles, il devient O(n^3)