algorithm - 在恒定时间内运行的分而治之算法？

Question

你能给我指出一个在恒定时间内运行的分而治之算法的例子吗？我处于一种“天哪!我想不出任何这样的事情”的情况。请指点我一些东西。谢谢

我知道遵循以下递归的算法:T(n) = 2T(n/2) + n 将是合并排序。我们将问题分成 2 个子问题——每个子问题的大小为 n/2。然后我们将花费 n 时间将所有内容重新合并到一个排序数组中。

我也知道 T(n) = T(n/2) + 1 将是 二进制搜索。

但是 T(n) = 1 是什么？

Answer 1

对于在恒定时间内运行的分而治之算法，它需要对任何输入执行不超过固定数量的工作。因此，它最多可以对任何输入进行固定次数的递归调用，因为如果调用次数没有限制，完成的总工作量就不会是常数。此外，它需要在所有这些递归调用中做大量的工作。

这基本上消除了任何看起来合理的递归关系。任何形式

T(n) = aT(n / b) + O(n^k)

立即就不可能了，因为递归调用的数量会随着输入 n 的增加而增加。

您可以制作一些在恒定时间内运行的高度人为设计的分而治之算法。例如，考虑这个问题:

Return the first element of the input array.

这在技术上可以用分而治之的方式解决，注意

• 单元素数组的第一个元素等于它本身。
• n 元素数组的第一个元素是第一个元素的子数组的第一个元素。

那么递归就是

T(n) = T(1) + O(1)

T(1) = 1

如您所见，这是一个看起来很奇怪的重复，但它确实有效。

我从来没有听说过在实践中会出现这样的事情，但如果我想到什么，我会尝试用细节更新这个答案。 (注意:我不希望更新此答案。^_^)

希望这对您有所帮助!