time-complexity - 分割数大于 n 的算法示例

Question

我正在使用树方法推导大师定理，我注意到了一些事情。

所以我们有：

$T(n)=a*T(n/b) + n^c$

由此：我们注意到，树的最后一层将有 $a^(log_b_n)$ 分裂，等于 $n^(log_b_a)$

现在，如果 $a=b$，我在最后一级得到 n 个拆分，这是我在快速排序和合并排序中看到的，如果 a

是否有大于 n 个拆分的实际示例？我们实际上在哪里重复元素的操作？

*此外，数学溢出格式似乎不起作用。如果有人提供帮助，将不胜感激。

Answer 1

通过分而治之的经典矩阵乘法就是这样一个例子。递归关系为：T(n)=8T(n/2)+ Theta(n^2)。另一个是Straussen 算法。

数学符号（遗憾地）仅限于少数几个 stackexchange 站点。