矩陣乘法結合律_矩陣乘法結合律分配律

很多朋友想了解關於矩陣的一些資料信息，下麵是(揚升資訊www.balincan8.com)小編整理的與矩陣相關的內容分享給大家，一起來看看吧。很多朋友想了解關於矩陣乘法的一些資料信息，下麵是(揚升資訊www.balincan8.com)小編整理的與矩陣乘法相關的內容分享給大家，一起來看看吧。

設想這樣一個場景，麵試官給了你一道算法題，你很快確定這是一道遞推問題，並給出了 O(n) 的解題方法，然而麵試官卻繼續問：“還能繼續優化嗎？”

這樣類似的場景並不少見，因為算法不僅追求「正確」，還追求「效率」，而這也正是優化方法的意義。

本文即將介紹的「矩陣快速冪」便是一種常見的優化遞推的方法，能將 O(n) 的遞推過程加速至 O(log(n))，使效率顯著提升。

一、矩陣運算

首先我們回顧一下「矩陣」，一個 n * m 的矩陣可以看作是一個 n * m 的二維數組，而矩陣的加減法就是將兩個矩陣對應位置上的數相加減，即 C = A + B 意味著矩陣 C 中任意一點

其中 A, B, C 均為 n * m 的矩陣，具體例子如下：

矩陣乘法的運算稍微複雜一些，假設 A 是 n * m 的矩陣，B 是 m * p 的矩陣，則 C = A * B 是 n * p 的矩陣，且對於 C 中任意一點

來說，滿足：

即 C 中第 i 行、第 j 列的元素等於 A 中第 i 行與 B 中第 j 列所有元素對應相乘再相加，這也就意味著矩陣相乘時，第一個矩陣的列數必須等於第二個矩陣的行數，具體例子如下：

另外，矩陣乘法滿足結合律，即 (A * B) * C = A * (B * C)，舉例如下：

滿足分配律，即 (A + B) * C = A * C + B * C，具體例子如下：

但不滿足交換律，即 A * B 不一定等於 B * A，具體例子如下：

代碼實現

我們將一個 n * m 的矩陣看作是一個 n * m 的二維數組，因此在 C++ 中我們用 vectorvectorint 來表示，矩陣相乘函數如下：

vectorvectorint matrix_multiply(vectorvectorint& a, vectorvectorint& b) { int n = a.size(), m = a[0].size(), p = b[0].size(); vectorvectorint c(n, vectorint(p, 0)); for (int i = 0; i n; i++) for (int j = 0; j p; j++) for (int k = 0; k m; k++) c[i][j] += a[i][k] * b[k][j]; return c;}

在 Python3 中我們用 List[List[int]] 來表示，矩陣相乘函數如下：

def matrix_multiply(a: List[List[int]], b: List[List[int]]) - List[List[int]]: n, m, p = len(a), len(a[0]), len(b[0]) c = [[0 for j in range(p)] for i in range(n)] for i in range(n): for j in range(p): for k in range(m): c[i][j] += a[i][k] * b[k][j] return c二、快速冪

講解「矩陣快速冪」前，我們需要回顧一下「快速冪」，完全沒有了解過的同學建議翻閱「刷算法題必備的數學考點匯總 」中相關內容。

簡單來說，「快速冪」就是通過將指數轉化為二進製，並以此來加快冪運算，例如 2^31 中 31 滿足：

其中 D 表示十進製，B 表示二進製。進一步地，2^31 的計算過程可以轉變為：

因此我們隻需從 1 開始計算 5 次求出

再將它們依次相乘，即可得到 2^31。

當計算 a^n（a 為任意實數）時，快速冪方法可以將原來的 O(n) 時間複雜度降低為 O(log(n))，從而大大加快指數運算。

三、矩陣快速冪

​接下來開始「矩陣快速冪」的介紹，首先以經典「斐波那契數列」為例進行講解。

509. 斐波那契數

題目描述

斐波那契數，通常用 F(n) 表示，形成的序列稱為斐波那契數列 。該數列由 0 和 1 開始，後麵的每一項數字都是前麵兩項數字的和。也就是：

F(0) = 0，F(1) = 1F(n) = F(n - 1) + F(n - 2)，其中 n 1

給你 n ，請計算 F(n) 。

示例 1

輸入：2輸出：1解釋：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2

輸入：3輸出：2解釋：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3

輸入：4輸出：3解釋：F(4) = F(3) + F(2) = 2 + 1 = 3解題思路

此題是經典的遞推問題，即

我們可以很輕鬆地在 O(n) 時間複雜度內求出

但假如 n 很大呢？

當 n = 1e9 時，顯然單純的遞推無法通過此題，因此我們用矩陣快速冪來加速遞推過程。

首先我們需要構造矩陣，令

則從

到

的轉移矩陣 B 為：

進一步地，我們可以得到：

由於矩陣乘法滿足結合律，因此矩陣 B 的冪次運算也可以通過「快速冪」進行加速，例如：

因此本題我們可以通過快速計算

再將其與矩陣

相乘，即可得到

將原來 O(n) 的遞推加速至 O(log(n)) 的這一過程即為「矩陣快速冪」。

另外，由於

中已包含

因此隻需計算

具體細節見代碼。

C++ 代碼class Solution {public: int fib(int n) { if (n 2) return n; vectorvectorint q{{1, 1}, {1, 0}}; vectorvectorint res = matrix_pow(q, n - 1); return res[0][0]; }​ vectorvectorint matrix_pow(vectorvectorint& a, int n) { vectorvectorint ret{{1, 0}, {0, 1}}; while (n 0) { if (n & 1) ret = matrix_multiply(ret, a); n = 1; a = matrix_multiply(a, a); } return ret; }​ vectorvectorint matrix_multiply(vectorvectorint& a, vectorvectorint& b) { int n = a.size(), m = a[0].size(), p = b[0].size(); vectorvectorint c(n, vectorint(p, 0)); for (int i = 0; i n; i++) for (int j = 0; j p; j++) for (int k = 0; k m; k++) c[i][j] += a[i][k] * b[k][j]; return c; }};Python3 代碼class Solution: def fib(self, n: int) - int: if n 2: return n q = [[1, 1], [1, 0]] res = self.matrix_pow(q, n - 1) return res[0][0] def matrix_pow(self, a: List[List[int]], n: int) - List[List[int]]: ret = [[1, 0], [0, 1]] while n 0: if n & 1: ret = self.matrix_multiply(ret, a) n = 1 a = self.matrix_multiply(a, a) return ret​ def matrix_multiply(self, a: List[List[int]], b: List[List[int]]) - List[List[int]]: n, m, p = len(a), len(a[0]), len(b[0]) c = [[0 for j in range(p)] for i in range(n)] for i in range(n): for j in range(p): for k in range(m): c[i][j] += a[i][k] * b[k][j] return c

運用「矩陣快速冪」加速遞推過程時，首先需要確定遞推公式，然後再根據遞推公式，確定矩陣

中究竟是

還是

或者包含更多。接下來再根據

和

確定轉移矩陣 B，最後應用快速冪計算 B 的冪次即可完成求解。

​接下來我們再通過一道例題加強對該解題思路的掌握。

麵試題 08.01. 三步問題

題目描述

三步問題。有個小孩正在上樓梯，樓梯有 n 階台階，小孩一次可以上 1 階、2 階或 3 階。實現一種方法，計算小孩有多少種上樓梯的方式。結果可能很大，你需要對結果模 1000000007。

示例 1輸入：n = 3 輸出：4說明: 有四種走法示例 2輸入：n = 5輸出：13解題思路

首先確定本題的遞推公式，令

表示上 n 階台階的方法數，則不難發現

接下來確定矩陣

首先假設

中僅包含

與

由於我們需要用

推出

根據之前的假設，

中僅包含

和

而推出

卻需要

和

因此假設不成立，即

中應該包含

即

​

由此我們可以確定轉移矩陣 B，即

由於求解

隻需求出

因此

中包含

根據題意可得：

由此使用快速冪求出

再與

相乘即可在 O(log(n)) 的時間複雜度內求出

另外本題需要對結果模 1000000007，即在矩陣乘法與最終答案計算時進行取模，具體細節見下述代碼。

C++ 代碼class Solution {public: typedef long long ll; static const int mod = 1e9 + 7; int waysToStep(int n) { if (n 3) return n; vectorvectorint q{{1, 1, 1}, {1, 0, 0}, {0, 1, 0}}; vectorvectorint res = matrix_pow(q, n - 2); ll ans = res[0][0] * 2ll + res[0][1] + res[0][2]; return ans % mod; }​ vectorvectorint matrix_pow(vectorvectorint& a, int n) { vectorvectorint ret = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; while (n 0) { if (n & 1) ret = matrix_multiply(ret, a); n = 1; a = matrix_multiply(a, a); } return ret; }​ vectorvectorint matrix_multiply(vectorvectorint& a, vectorvectorint& b) { int n = a.size(), m = a[0].size(), p = b[0].size(); vectorvectorint c(n, vectorint(p, 0)); for (int i = 0; i n; i++) for (int j = 0; j p; j++) for (int k = 0; k m; k++) c[i][j] = (c[i][j] + (ll)a[i][k] * (ll)b[k][j] % mod) % mod; return c; }};Python3 代碼class Solution: def waysToStep(self, n: int) - int: if n 3: return n q = [[1, 1, 1], [1, 0, 0], [0, 1, 0]] res = self.matrix_pow(q, n - 2) ans = res[0][0] * 2 + res[0][1] + res[0][2] return ans % 1000000007 def matrix_pow(self, a: List[List[int]], n: int) - List[List[int]]: ret = [[1, 0, 0], [0, 1, 0], [0, 0, 1]] while n 0: if n & 1: ret = self.matrix_multiply(ret, a) n = 1 a = self.matrix_multiply(a, a) return ret​ def matrix_multiply(self, a: List[List[int]], b: List[List[int]]) - List[List[int]]: n, m, p = len(a), len(a[0]), len(b[0]) c = [[0 for j in range(p)] for i in range(n)] for i in range(n): for j in range(p): for k in range(m): c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % 1000000007 return c總結

「矩陣快速冪」是一種常見的遞推優化方法，可以將 O(n) 的遞推優化至 O(log(n))，具體算法流程如下：

確定遞推式確定矩陣 An 的維數根據 An 和

確定轉移矩陣 B

4.快速冪計算轉移矩陣 B 的冪次

5.將 B 的冪次運算結果與A0 相乘得到最終答案 Fn

本文作者：Gene_Liu

聲明：本文歸 “力扣” 版權所有，如需轉載請聯係。

本文到此結束，希望對大家有所幫助呢。