分而治之算法中的时间复杂度

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

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

2011-12-21 Aj Gauravdeep

那么解释一下，我们实际上需要知道你目前的理解水平。例如，您一般对递归算法和复杂性分析的实力。我建议你尝试查找一些互动幻灯片。 – 2011-12-21 08:45:38

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

如何计算时间复杂度：假设您的算法花费的时间是T（n）。注意，所花费的时间是问题大小即n的函数。

现在，注意你在做什么。你把问题分解成k个部分，每个部分的大小为n/k（它们的大小可能不相同，在这种情况下，你必须单独添加它们所花费的时间）。现在，你会解决这些k部分。每个部分所花费的时间将是T（n/k），因为问题的大小现在减小到n/k。你正在解决这些问题。所以，它需要k * T（n/k）时间。

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

因此，通过你的算法采取的总时间为： T（N）=（K * T（N/K））+ O（F（N））

你已经有了一个递推关系现在你可以解决得到T（n）。

来源

2011-12-21 08:51:39 Divya

随时要求澄清。 – Divya 2011-12-21 08:53:13

谢谢Divya。雅，我去了那个网站，看起来已经达到了它的容量，因此无法提供服务。其实你解释我已经知道，直到那一部分，但是，它的数学令我困惑。但是，我的老大学书籍，并试图了解。非常感谢您的时间。 – 2011-12-22 03:11:09

如果你正在寻找“如何解决复发关系”，你可能想要检查这个链接http://www.cs.ucr.edu/~jiang/cs141/recur-tut.txt这是一个快速教程涵盖解决复发关系的各种方法。乐于帮助！ :) @Leoheart – Divya 2011-12-22 03:47:32

作为该链接表示：

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

为T(2)，它与返回之前比较单一的位置。对于T(1)这是一个没有任何比较的基础。
对于T(n)：你递归调用该方法对数组的两半，比较两个（最小值，最大值）元组找到真正的最小值和最大值，它给你上面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
（*）诱导的假设，是真实的，因为

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

来源

2011-12-21 09:01:58 amit

嗨，我们如何用k + 1项来证明这个证明？ – RichArt 2017-08-13 01:41:26

分而治之算法中的时间复杂度

回答

相关问题