1

您能否帮助我理解分治算法的时间复杂度。

让我们以这个为例。 http://www.geeksforgeeks.org/archives/4583方法2：它给了T(n) = 3/2n -2，我不明白为什么？

对不起，如果我也给了你一个额外的页面来打开，但我真的想至少理解一个很好的高层次，这样我就可以自己找到这些算法的复杂性，你的回答非常感谢。

4

2 回答 2

2

由于某种原因无法打开此链接。我还是会试一试的。当您使用分而治之的策略时，您所做的就是将问题分解为许多较小的问题，然后将小问题的解决方案组合起来以获得主要问题的解决方案。如何解决较小的问题：通过进一步分解它们。这个分解过程一直持续到你达到问题小到可以直接处理的程度。

如何计算时间复杂度：假设你的算法花费的时间是 T(n)。请注意，所用时间是问题大小 ien 的函数

现在，注意你在做什么。您将问题分解为每个大小为 n/k 的 k 个部分（它们的大小可能不相等，在这种情况下，您必须单独添加它们所花费的时间）。现在，您将解决这 k 个部分。每个部分所花费的时间将是 T(n/k)，因为现在问题大小已减少到 n/k。你正在解决其中的 k 个问题。因此，需要 k * T(n/k) 时间。

在解决了这些小问题之后，您将结合他们的解决方案。这也需要一些时间。那个时间将再次成为您问题大小的函数。（它也可以是恒定的）。设该时间为 O(f(n))。

因此，您的算法所花费的总时间为：T(n) = (k * T(n/k)) + O(f(n))

你现在有一个递归关系，你可以求解得到 T(n)。

于 2011-12-21T08:51:39.977 回答
2

如此链接所示：

  T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
  T(2) = 1
  T(1) = 0

对于T(2)，它是返回前进行​​单一比较的基数。因为T(1)它是没有任何可比性的基础。
For T(n)：您递归地调用数组的两半的方法，并比较两个 (min,max) 元组以找到真正的最小值和最大值，这给了你上面的T(n)等式

If n is a power of 2, then we can write T(n) as:

   T(n) = 2T(n/2) + 2

这很好地解释了自己。

  T(n)  = 3/2n -2

在这里，你用归纳法解决它：
基本情况：对于 n = 2：T(2) = 1 = (3/2)*2 -2
我们假设T(k) = (3/2)k - 2每个k < n
T(n) = 2T(n/2) + 2 = (*) 2*((3/2*(n/2)) -2) + 2 = 3*(n/2) -4 + 2 = (3/2)*n -2
(*) 归纳假设都是正确的，因为n/2 < n

因为我们证明了归纳是正确的，所以我们可以得出结论：T(n) = (3/2)n - 2

于 2011-12-21T09:01:58.120 回答