—
Két -es mátrix szorzása hagyományos módszerrel időbonyolultságú, mivel minden mátrixelem kiszámításához szorzás és összeadás szükséges.
Strassen algoritmusa optimalizálja ezt a folyamatot, és a komplexitást -re csökkenti.
—
—
- **Rekurzív felosztás**: - Az algoritmus minden lépésben szorzást és összeadást/levonást végez. - **Összkomplexitás**: Ez a **Master-tétel** alapján:
—
—
import numpy as np
def add_matrix(A, B):
return np.add(A, B)
def sub_matrix(A, B):
return np.subtract(A, B)
def strassen(A, B):
n = A.shape
if n == 1:
return A * B
k = n // 2
# Mátrixok felosztása
A11, A12, A21, A22 = A, A, A, A
B11, B12, B21, B22 = B, B, B, B
# Strassen-féle szorzások
M1 = strassen(add_matrix(A11, A22), add_matrix(B11, B22))
M2 = strassen(add_matrix(A21, A22), B11)
M3 = strassen(A11, sub_matrix(B12, B22))
M4 = strassen(A22, sub_matrix(B21, B11))
M5 = strassen(add_matrix(A11, A12), B22)
M6 = strassen(sub_matrix(A21, A11), add_matrix(B11, B12))
M7 = strassen(sub_matrix(A12, A22), add_matrix(B21, B22))
# Mátrix blokkok összeállítása
C11 = add_matrix(sub_matrix(add_matrix(M1, M4), M5), M7)
C12 = add_matrix(M3, M5)
C21 = add_matrix(M2, M4)
C22 = add_matrix(sub_matrix(add_matrix(M1, M3), M2), M6)
# Mátrixok összeillesztése
C = np.zeros((n, n))
C, C, C, C = C11, C12, C21, C22
return C
# Példa használat
A = np.array(, ])
B = np.array(, ])
C = strassen(A, B)
print("A × B =")
print(C)
Kimenet:
A × B = ]
#include <iostream>
#include <vector>
using namespace std;
using Matrix = vector<vector<int>>;
Matrix add_matrix(const Matrix& A, const Matrix& B) {
int n = A.size();
Matrix C(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
C = A + B;
return C;
}
Matrix sub_matrix(const Matrix& A, const Matrix& B) {
int n = A.size();
Matrix C(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
C = A - B;
return C;
}
Matrix strassen(const Matrix& A, const Matrix& B) {
int n = A.size();
if (n == 1) {
return {{A * B}};
}
int k = n / 2;
Matrix A11(k, vector<int>(k)), A12(k, vector<int>(k)),
A21(k, vector<int>(k)), A22(k, vector<int>(k)),
B11(k, vector<int>(k)), B12(k, vector<int>(k)),
B21(k, vector<int>(k)), B22(k, vector<int>(k));
for (int i = 0; i < k; ++i) {
for (int j = 0; j < k; ++j) {
A11 = A;
A12 = A;
A21 = A;
A22 = A;
B11 = B;
B12 = B;
B21[j
] = B;
B22 = B;
}
}
auto M1 = strassen(add_matrix(A11, A22), add_matrix(B11, B22));
auto M2 = strassen(add_matrix(A21, A22), B11);
auto M3 = strassen(A11, sub_matrix(B12, B22));
auto M4 = strassen(A22, sub_matrix(B21, B11));
auto M5 = strassen(add_matrix(A11, A12), B22);
auto M6 = strassen(sub_matrix(A21, A11), add_matrix(B11, B12));
auto M7 = strassen(sub_matrix(A12, A22), add_matrix(B21, B22));
Matrix C(n, vector<int>(n));
for (int i = 0; i < k; ++i) {
for (int j = 0; j < k; ++j) {
C = M1 + M4 - M5 + M7;
C = M3 + M5;
C = M2 + M4;
C = M1 - M2 + M3 + M6;
}
}
return C;
}
int main() {
Matrix A = {{1, 2}, {3, 4}};
Matrix B = {{5, 6}, {7, 8}};
Matrix C = strassen(A, B);
cout << "A × B = " << endl;
for (const auto& row : C) {
for (int val : row)
cout << val << " ";
cout << endl;
}
return 0;
}
Kimenet:
A × B = 19 22 43 50
A Strassen-algoritmus hatékony módszer a mátrixszorzás gyorsítására, amely csökkenti a számítási költségeket nagy mátrixok esetén. Bár komplexebb, mint a hagyományos módszer, jelentős előnyt nyújt modern alkalmazásokban.