Algorithme de Strassen pour l'analyse de la complexité de la multiplication matricielle

8

Je vois partout que l'équation récursive de la complexité de Strassen alg est: Ce n'est pas si clair pour moi. Le paramètre est censé être la taille de l'entrée, mais il semble qu'il s'agit ici d'une dimension d'une matrice alors que la taille de l'entrée est en fait . De plus, chaque matrice de l'entrée est divisée en 4 sous-matrices, il semble donc que l'équation récursive devrait être

T(n)=7T(n2)+O(n2).
nn2
T(n)=7T(n4)+O(n).

dafnahaktana
la source

Réponses:

13

C'est vrai que le paramètrenindique généralement la taille de l'entrée, mais ce n'est pas toujours le cas. Pour la multiplication à matrice carrée,nindique le nombre de lignes (ou colonnes). Pour les graphiques,n désigne souvent le nombre de sommets, et mle nombre d'arêtes. Pour les algorithmes sur les fonctions booléennes,n indique le nombre d'entrées, bien que la table de vérité elle-même ait une taille 2n. Il y a beaucoup d'autres exemples.

Yuval Filmus
la source
5

C'est de retour à la taille de la matrice. Supposons que la matrice d'origine soitn×n. Par conséquent, nous considéreronsT(n) comme un calcul de deux matrices de taille n×n. Lorsque nous divisons la matrice d'origine en 4 parties, la taille de chaque partie estn2×n2. Par conséquent, le coût de calcul de la multiplication de deux matrices avec cette taille estT(n2).

OMG
la source
0

La complexité temporelle est souvent basée sur la taille d'entrée, mais ce n'est pas une exigence absolue. Dans ce cas, pour la multiplication des matrices nxn, il semble plus naturel de compter le nombre d'opérations sur la base de n, pas sur la taille du problème nx n.

gnasher729
la source