查找算法的复发关系

StackOverflow https://stackoverflow.com/questions/2919698

  •  05-10-2019
  •  | 
  •  

题

我正在阅读我的算法教科书，并且正在阅读有关复发关系并找到算法的大复杂性。我穿过这条线 

"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的来源吗？

有帮助吗？

解决方案

合并排序算法可以总结为：

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

有一个o（n）算法以合并两个长度n，即其复杂性是 BN 对于一些常数 b > 0.

假设复杂性 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情况（您停止递归的基本情况）是微不足道的。

其他提示

好吧，这一说法是（大概）讨论的结论，或者至少是有关算法的陈述。没有细节，我只能做出有根据的猜测，这会像这样：

  • 该算法要做的第一件事是检查是否被要求处理0或1个元素。如果这是真的，它将立即返回。因此， n < 2, ，有固定成本 - 称呼它 b
  • 为了 n >= 2, ，该算法将其输入分为两部分，每个部分 n/2, 并在每件作品上自动起来。每个这样的调用都会成本 t(n/2), ，有两个这样的调用
  • 然后还有一笔额外的费用将两部分合并在一起 - 此费用将与 n - 称它为 b 时代 n

唯一的唯一奇怪性是，为什么出现的两个常数因素应该相同并不是完全明显的 - 但是BIG -O分析点的一部分是，最终不变的因素最终并不重要。

T(n) = c if n < d
     = A*T(n/b) + f(n)

其中d> = 1，并且有一个子问题，并且子问题最多为N/B大小。 F（n）是将问题分为子问题并将子问题解决方案合并为整个问题的解决方案所需的总额外时间。

这是用于划分和征服算法。

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top