1

我正在阅读我的算法教科书，并且正在阅读有关递归关系并发现算法复杂度大的问题。我跑过这条线

"In the case of the merge-sort algorithm, we get the recurrence equation:

    t(n) = b                  if n < 2

         = 2t(n/2) +bn        if n >= 2

for b > 0

我的回答是“我们怎么知道的？！？！”

所以我想知道是否有一种系统的方法，或者只是一种从算法中获取这些递归关系的合乎逻辑的方法

有人可以解释 b 和两个 2 的来源吗？

4

3 回答 3

1

归并排序算法可以概括为：

mergesort (array A) {
   mergesort (first half of A);
   mergesort (second half of A);
   merge the two halves and return;
}

有一个 O(N) 算法来合并两个长度为 N 的数组，即对于某个常数b > 0 ，它的复杂度是bN 。

假设复杂度mergesort为 T(N)。由于 N 的一半是 N/2，我们看到：

mergesort (array A) {                    T(N)    =
   mergesort (first half of A);          T(N/2)  +
   mergesort (second half of A);         T(N/2)  +
   merge the two halves and return;       bN
}

这解释了 N ≥ 2 的情况。

N < 2 情况（停止递归的基本情况）是微不足道的。

于 2010-05-27T09:02:35.270 回答
1

好吧，这个陈述（大概）是讨论的结论，或者至少是对所讨论算法的陈述。如果没有详细信息，我只能做出有根据的猜测，如下所示：

  • 算法做的第一件事是检查它是否被要求处理 0 或 1 个元素。如果这是真的，它会立即返回。因此，n < 2有一个固定成本——称之为b
  • 对于n >= 2，该算法将其输入分成两块，每块大小为n/2，并在每一块上调用自身。每个这样的调用将花费t(n/2)，并且有两个这样的调用
  • 然后将两个部分重新合并在一起需要额外的成本 - 这个成本将与n- 称之为b时间n

唯一有点奇怪的是，为什么出现的两个常数因素应该相同并不完全清楚——但大 O 分析的部分要点是常数因素最终无关紧要。

于 2010-05-27T09:01:20.117 回答
0 
T(n) = c if n < d
     = A*T(n/b) + f(n)

其中 d>=1 并且存在 A 子问题，并且子问题最多为 n/b 大小。f(n) 是将问题划分为子问题并将子问题解决方案合并为整个问题的解决方案所需的总额外时间。

这是针对分而治之的算法。

我想知道为什么合并排序中有 2 个子问题？

于 2010-05-27T09:12:32.200 回答