algorithm - 分治算法的复杂性

Question

假设输入问题的大小随着整数 n 的增加而增加。令 T(n) 为解决此问题的分治算法的时间复杂度。那么 T(n) 满足以下形式的方程：

T(n) = a T(n/b) + f (n)。

现在我的问题是：a 和 b 怎么可能不相等？

似乎它们应该相等，因为递归调用的数量必须等于 b（子问题的大小）。

标签： algorithm

Answer 1

在软件中，时间经常被浪费在控制操作上，比如函数调用。所以通常 a > b。

此外，在某些情况下，问题只需要一个“递归调用”（然后就是迭代），例如二进制搜索。在这些情况下，a < b。