@Sherlockyang 2018-03-20T12:24:51.000000Z 字数 232 阅读 369

Divide-and-Conquer

算法分析与设计

$x = 2^{\frac{n}{2}}x_1+x_0$

$y = 2^{\frac{n}{2}}y_1+y_0$

矩阵乘法 $C=AB$ $A,B \in R^{n\times n}$

$c_{ij} = \sum^n_{i=k}a_{ik}b{_{kj}}$ where bigO =

$O(n^3)$

可将矩阵转换成7个矩阵的乘法。和18个矩阵的加减法。

$T(n) = 7T(\frac{n}{2})+O(n^{2})\Rightarrow T(n) = n^{\log_2{7}}$

添加新批注

在作者公开此批注前，只有你和作者可见。

回复批注