单选题：给定两个 $$n\times n$$ 的矩阵 $$A$$ 和 $$B$$。考虑下列计算矩阵乘积 $$C = A \cdot B$
给定两个 $$n\times n$$ 的矩阵 $$A$$ 和 $$B$$。考虑下列计算矩阵乘积 $$C = A \cdot B$$ 的分治法。
将每个矩阵划分为如下四个 $$\frac{n}{2}\times\frac{n}{2}$$ 的子矩阵：
$$\begin{bmatrix} C_1 & C_2 \\ C_3 & C_4\end{bmatrix}$$ = $$\begin{bmatrix} A_1 & A_2 \\ A_3 & A_4 \end{bmatrix} \cdot \begin{bmatrix} B_1 & B_2\\ B_3 & B_4 \end{bmatrix}$$
定义 $$P_1, P_2, \cdots ,P_7$$ 如下：
$$P_1 = A_1\cdot(B_2-B_4) $$
$$ P_2 = (A_1+A_2)\cdot B_4$$
$$ P_3 = (A_3+A_4)\cdot B_1 $$
$$ P_4 = A_4\cdot(B_3-B_1) $$
$$ P_5 = (A_1+A_4)\cdot(B_1+B_4) $$
$$ P_6 = (A_2-A_4)\cdot(B_3+B_4) $$
$$ P_7 = (A_1-A_3)\cdot(B_1+B_2) $$
这里所有的矩阵乘法都是**递归**完成的。矩阵 $$C$$ 的每一块都可以利用 $$P_1, P_2, \cdots ,P_7$$ 通过加减运算得到。
以下哪一项最接近实际的算法时间复杂度？ @[C](3)
A. $$O(n^2\log_2 n)$$
B. $$O(n^e)$$
C. $$O(n^{\log_2 7})$$
D. $$O(n^3)$$
A.$$O(n^2\log_2 n)$$
B.$$O(n^e)$$
C.$$O(n^{\log_2 7})$$
D.$$O(n^3)$$
答案：C
将每个矩阵划分为如下四个 $$\frac{n}{2}\times\frac{n}{2}$$ 的子矩阵：
$$\begin{bmatrix} C_1 & C_2 \\ C_3 & C_4\end{bmatrix}$$ = $$\begin{bmatrix} A_1 & A_2 \\ A_3 & A_4 \end{bmatrix} \cdot \begin{bmatrix} B_1 & B_2\\ B_3 & B_4 \end{bmatrix}$$
定义 $$P_1, P_2, \cdots ,P_7$$ 如下：
$$P_1 = A_1\cdot(B_2-B_4) $$
$$ P_2 = (A_1+A_2)\cdot B_4$$
$$ P_3 = (A_3+A_4)\cdot B_1 $$
$$ P_4 = A_4\cdot(B_3-B_1) $$
$$ P_5 = (A_1+A_4)\cdot(B_1+B_4) $$
$$ P_6 = (A_2-A_4)\cdot(B_3+B_4) $$
$$ P_7 = (A_1-A_3)\cdot(B_1+B_2) $$
这里所有的矩阵乘法都是**递归**完成的。矩阵 $$C$$ 的每一块都可以利用 $$P_1, P_2, \cdots ,P_7$$ 通过加减运算得到。
以下哪一项最接近实际的算法时间复杂度？ @[C](3)
A. $$O(n^2\log_2 n)$$
B. $$O(n^e)$$
C. $$O(n^{\log_2 7})$$
D. $$O(n^3)$$
A.$$O(n^2\log_2 n)$$
B.$$O(n^e)$$
C.$$O(n^{\log_2 7})$$
D.$$O(n^3)$$
答案：C