使用分而治之的矩阵乘法,时间复杂度

Question

据我所知,该算法使用8次乘法和4次加时间复杂度:

乘法在每个n/2 * n/2矩阵上完成.我对此几乎没有问题:

1. 每个n * n矩阵最终都会n=1通过执行来缩小尺寸T(n/2)吗？如果这样返回a11*b11似乎毫无意义好像回到1*6了a11*b11为以下矩阵:

然后基本情况应该n==2执行else部分,因为下面的操作似乎是合法的.

2. 为什么增加部分采取0(n^2)？我的意思是,我们完全没有处理矩阵加法,而仅仅是数字,因为每个矩阵都减少到2 * 2如下:

那么加法部分应该只贡献4个？(为什么0(n^2)？)

Answer 1

如果我正确理解了这个问题，那么这些部分可以回答如下。

1. 事实上，所有矩阵最终都会简化为1*1矩阵；这应该不会太令人惊讶，因为矩阵乘法的基本定义最终是根据底层环的乘法来定义的。

2. 加法部分0(n^2)在递归的每个级别上都具有复杂性，因为加法是对乘法的递归评估的结果执行的。