C++ 中的 Strassen 算法

2025年5月13日 | 阅读 9 分钟

引言

Strassen 算法 由 **Volker Strassen** 于 **1969** 年提出，它通过引入一种高效的方法革新了矩阵乘法，尤其对大型矩阵特别有益。与标准乘法算法不同，Strassen 算法战略性地减少了所需的乘法次数。核心思想是将矩阵乘积表示为较小乘法的形式，采用分治策略。通过递归地将矩阵分解为四个象限，该算法实现了更少的乘法次数，从而提高了计算效率。这种创新技术已在各种领域得到应用，并且仍然是算法优化中的一个基石。Strassen 算法在复杂性和性能之间取得了平衡，突显了算法创新策略的重要性。

程序

#include <iostream>
#include <vector>
using namespace std;
// Function to add two matrices
void matrixAddition(const vector<vector<int>>& A, const vector<vector<int>>& B, vector<vector<int>>& C, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            C[i][j] = A[i][j] + B[i][j];
        }
    }
}
// Function to subtract one matrix from another
void matrixSubtraction(const vector<vector<int>>& A, const vector<vector<int>>& B, vector<vector<int>>& C, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            C[i][j] = A[i][j] - B[i][j];
        }
    }
}
// Function to multiply two matrices using Strassen's algorithm
void strassenMultiplication(const vector<vector<int>>& A, const vector<vector<int>>& B, vector<vector<int>>& C, int n) {
    if (n == 1) {
        C[0][0] = A[0][0] * B[0][0];
        return;
    }
    // Split matrices into quadrants
    int newSize = n / 2;
    vector<vector<int>> A11(newSize, vector<int>(newSize));
    vector<vector<int>> A12(newSize, vector<int>(newSize));
    vector<vector<int>> A21(newSize, vector<int>(newSize));
    vector<vector<int>> A22(newSize, vector<int>(newSize));
    vector<vector<int>> B11(newSize, vector<int>(newSize));
    vector<vector<int>> B12(newSize, vector<int>(newSize));
    vector<vector<int>> B21(newSize, vector<int>(newSize));
    vector<vector<int>> B22(newSize, vector<int>(newSize));
    vector<vector<int>> C11(newSize, vector<int>(newSize));
    vector<vector<int>> C12(newSize, vector<int>(newSize));
    vector<vector<int>> C21(newSize, vector<int>(newSize));
    vector<vector<int>> C22(newSize, vector<int>(newSize));
    // Populate quadrants
    for (int i = 0; i < newSize; ++i) {
        for (int j = 0; j < newSize; ++j) {
            A11[i][j] = A[i][j];
            A12[i][j] = A[i][j + newSize];
            A21[i][j] = A[i + newSize][j];
            A22[i][j] = A[i + newSize][j + newSize];
            B11[i][j] = B[i][j];
            B12[i][j] = B[i][j + newSize];
            B21[i][j] = B[i + newSize][j];
            B22[i][j] = B[i + newSize][j + newSize];
        }
    }
    // Compute intermediate matrices 
    vector<vector<int>> P1(newSize, vector<int>(newSize));
    vector<vector<int>> P2(newSize, vector<int>(newSize));
    vector<vector<int>> P3(newSize, vector<int>(newSize));
    vector<vector<int>> P4(newSize, vector<int>(newSize));
    vector<vector<int>> P5(newSize, vector<int>(newSize));
    vector<vector<int>> P6(newSize, vector<int>(newSize));
    vector<vector<int>> P7(newSize, vector<int>(newSize));
    matrixAddition(A11, A22, P1, newSize);
    matrixAddition(B11, B22, P2, newSize);
    matrixAddition(A21, A22, P3, newSize);
    matrixSubtraction(B12, B22, P4, newSize);
    matrixSubtraction(B21, B11, P5, newSize);
    matrixAddition(A11, A12, P6, newSize);
    matrixSubtraction(A21, A11, P7, newSize);
    // Recursively compute products
    strassenMultiplication(P1, P2, C11, newSize);
    strassenMultiplication(P3, B11, C12, newSize);
    strassenMultiplication(A11, P4, C21, newSize);
    strassenMultiplication(A22, P5, C22, newSize);
    strassenMultiplication(P6, P7, C11, newSize);
    matrixAddition(C11, P3, C12, newSize);
    matrixSubtraction(C21, P2, C21, newSize);
    matrixAddition(C22, P1, C22, newSize);
    // Combine quadrants into the result
    for (int i = 0; i < newSize; ++i) {
        for (int j = 0; j < newSize; ++j) {
            C[i][j] = C11[i][j];
            C[i][j + newSize] = C12[i][j];
            C[i + newSize][j] = C21[i][j];
            C[i + newSize][j + newSize] = C22[i][j];
        }
    }
}
int main() {
    // Example usage
    int n = 4;  // Size of matrices (should be a power of 2 for Strassen's algorithm)
    vector<vector<int>> A = {{1, 2, 3, 4},
                             {5, 6, 7, 8},
                             {9, 10, 11, 12},
                             {13, 14, 15, 16}};
    vector<vector<int>> B = {{17, 18, 19, 20},
                             {21, 22, 23, 24},
                             {25, 26, 27, 28},
                             {29, 30, 31, 32}};
    vector<vector<int>> C(n, vector<int>(n, 0));
    strassenMultiplication(A, B, C, n);
    // Print the result
    cout << "Matrix A:" << endl;
    for (const auto& row : A) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "\nMatrix B:" << endl;
    for (const auto& row : B) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "\nMatrix C (Result of A * B using Strassen's algorithm):" << endl;
    for (const auto& row : C) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

输出

Matrix A:
1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16 
Matrix B:
17 18 19 20 
21 22 23 24 
25 26 27 28 
29 30 31 32 
Matrix C (Result of A * B using Strassen's algorithm):
80 106 100 128 
-16 18 12 48 
-32 -23 104 137 
-36 -47 4 49

说明

矩阵加法和减法函数

程序首先定义了加法和减法矩阵的函数。这些函数接受两个矩阵 (A 和 B) 作为输入，执行相应的操作，并将结果存储在另一个矩阵 (C) 中。

Strassen 乘法函数

程序的主要焦点是 **strassenMultiplication** 函数，它实现了 Strassen 算法进行矩阵乘法。

如果矩阵是 1x1（基本情况），函数将直接计算乘积并返回。

否则，它将输入矩阵分割成四个象限，并执行一系列矩阵运算来计算中间矩阵 (P1 到 P7)。

递归地，它应用 Strassen 算法来计算这些中间矩阵。

最后，它将这些中间矩阵组合起来形成结果矩阵 (C)。

主函数

在 main 函数中，使用示例值初始化矩阵 A 和 B。

然后，程序创建一个大小相同的空矩阵 C，用于存储使用 Strassen 算法乘法 A 和 B 的结果。

调用 strassenMultiplication 函数，传入矩阵 A、B 和空矩阵 C。

示例用法

程序打印原始矩阵 A 和 B，以及结果矩阵 C。

这演示了 Strassen 算法在执行矩阵乘法方面的正确性。

关于矩阵大小的说明

有一个注释指出，为了使 Strassen 算法效率最高，矩阵的大小应该是 2 的幂。这是因为该算法会递归地将矩阵分割成更小的矩阵，直到它们变成 1x1，这是基本情况。

理解结果

矩阵乘法 (C) 的结果被打印到控制台，显示了 Strassen 算法如何对矩阵 A 和 B 执行乘法运算。

复杂度分析

时间复杂度

Strassen 算法的矩阵乘法时间复杂度为 O(n^log2(7))，其中 n 是矩阵的大小。

在每个递归步骤中，该算法执行常数次的矩阵加法、减法和乘法。总共有七个此类递归调用（P1 到 P7），导致时间复杂度中的 log2(7) 指数。

空间复杂度

Strassen 算法的空间复杂度为 O(n^2)，因为在递归调用期间需要存储中间矩阵。

在每次递归调用中，该算法都需要额外的空间来存储 P1 到 P7 以及用于计算的子矩阵。

空间复杂度受递归深度影响，对于大小为 n 的矩阵，递归深度为 log2(n)。总体空间复杂度为 O(n^2 log2(n))。

方法 1：传统矩阵乘法

此方法通过三个嵌套循环直接实现矩阵乘法。虽然对于大型矩阵不如 Strassen 算法高效，但它简单易懂。

程序

#include <iostream>
#include <vector>
using namespace std;
void matrixMultiplication(const vector<vector<int>>& A, const vector<vector<int>>& B, vector<vector<int>>& C, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            C[i][j] = 0;
            for (int k = 0; k < n; ++k) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}
int main() {
    // Example usage
    int n = 4;  // Size of matrices
    vector<vector<int>> A = {{1, 2, 3, 4},
                             {5, 6, 7, 8},
                             {9, 10, 11, 12},
                             {13, 14, 15, 16}};
    vector<vector<int>> B = {{17, 18, 19, 20},
                             {21, 22, 23, 24},
                             {25, 26, 27, 28},
                             {29, 30, 31, 32}};
    vector<vector<int>> C(n, vector<int>(n, 0));
    matrixMultiplication(A, B, C, n);
    // Print the result
    cout << "Matrix A:" << endl;
    for (const auto& row : A) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "\nMatrix B:" << endl;
    for (const auto& row : B) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "\nMatrix C (Result of A * B using traditional multiplication):" << endl;
    for (const auto& row : C) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

输出

Matrix A:
1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16 
Matrix B:
17 18 19 20 
21 22 23 24 
25 26 27 28 
29 30 31 32 
Matrix C (Result of A * B using traditional multiplication):
250 260 270 280 
618 644 670 696 
986 1028 1070 1112 
1354 1412 1470 1528

说明

输入矩阵

我们从两个输入矩阵开始，称之为矩阵 A 和矩阵 B。每个矩阵本质上是由数字组成的网格，按行和列排列。

结果矩阵初始化

我们创建一个空矩阵，称之为矩阵 C，用于存储乘法结果。矩阵 C 将具有与矩阵 A 相同的行数和与矩阵 B 相同的列数。

用于乘法的嵌套循环

我们使用三个嵌套循环来遍历矩阵 A、B 和 C 的行和列。

最外层循环遍历矩阵 A 的行。

中间循环遍历矩阵 B 的列。

最内层循环负责计算矩阵 C 的单个元素。

乘法和累加

对于矩阵 C 中的每个元素，我们执行一系列乘法和加法。

矩阵 C 中位于第 i 行第 j 列的元素是通过将矩阵 A 的第 i 行的每个元素与矩阵 B 的第 j 列的相应元素相乘，然后将结果相加来计算的。

填充结果矩阵

在遍历嵌套循环的过程中，我们根据指定的乘法和加法运算来计算并填充矩阵 C 的每个元素。

完成乘法

在完成嵌套循环的所有迭代后，矩阵 C 已根据矩阵乘法运算的结果完全填充。

输出

最终矩阵 C 是通过传统乘法方法将矩阵 A 乘以矩阵 B 的结果。

复杂度分析

时间复杂度

传统矩阵乘法算法的时间复杂度为 O(n^3)，其中 n 是矩阵的大小。

这种立方时间复杂度源于，对于结果矩阵中的每个元素，我们在嵌套循环中执行 n 次乘法和 n 次加法。由于我们有

n^2 个元素需要计算在结果矩阵中，因此总时间复杂度为

O(n^3)。

空间复杂度

空间复杂度为 O(n^2)，因为它取决于结果矩阵的大小。

该算法除了输入矩阵 A 和 B 之外，不需要与输入大小 (n) 成比例的额外空间。相反，它使用空间来存储结果矩阵 C，该矩阵有 n^2 个元素。

空间复杂度通常由结果矩阵的存储要求主导。

性质

C++ 中 Strassen 算法有几个属性。Strassen 算法的一些属性如下：

分而治之

Strassen 算法遵循分治策略，将矩阵乘法问题分解为更小的子问题。

它递归地将大型矩阵分割成更小的矩阵，直到达到基本情况（例如，大小为 1x1 的矩阵）。

减少乘法次数

Strassen 算法的主要优点之一是它能够减少与标准立方时间复杂度相比的乘法次数。

与朴素方法中的八次乘法相比，Strassen 算法仅使用七次乘法，从而提高了大型矩阵的效率。

递归深度

Strassen 算法的递归深度为 log2(7)，因为它在每个递归步骤中将矩阵分割成更小的象限。

递归性质可以有效地计算中间矩阵。

优化的加法和减法

Strassen 算法采用加法和减法的组合来有效地计算中间矩阵。

这些操作有助于降低整体计算成本。

2 的幂次的矩阵大小

当应用于维度为 2 的幂次的矩阵时，Strassen 算法最有效。

如果输入矩阵的大小不是 2 的幂次，则可能需要进行填充或调整大小。

在并行计算中的应用

Strassen 算法非常适合并行计算环境，因为每个递归调用都可以独立执行。

并行化该算法可以进一步提高非常大矩阵的效率。

下一个主题Minimum-genetic-mutation-in-cpp

C++ 中的 Strassen 算法

引言

程序

方法 1：传统矩阵乘法

程序

性质

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中的 Strassen 算法

引言

程序

方法 1：传统矩阵乘法

程序

性质

相关帖子

C++ 编译器

使用 C++ 进行 CSV 文件管理

C++ std::chi_squared_distribution

C++ 中的自递归模板模式 (CRTP)

C++ Dancing Links 算法 (DLX)

C++ 中的接雨水

C++ 中每个节点的下一个右侧指针填充

C++ 生命游戏算法

C++ 中的奇数数字

C++ 中矩阵中最短的获得食物的路径

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题