分而治之算法的时间复杂度
您能帮我理解分而治之算法的时间复杂度吗？
我们以这个为例。 http://www.geeksforgeeks.org/archives/4583 方法2： 它给出了 T(n) = 3/2n -2 我不明白为什么？
很抱歉，如果我给了您一个额外的页面来打开，但我真的想至少理解到一个很好的高水平，以便我可以自己找到此类算法的复杂性，非常感谢您的回答。
Could you please help me in understanding the Time Complexity for Divide and Conquer algorithm.
Let's take example of this one.
http://www.geeksforgeeks.org/archives/4583 Method 2:
It gave T(n) = 3/2n -2 and i don't understand why?
I am sorry, if i gave you an extra page to open too but i really wanna understand atleast to a good high level so that i can find the complexity of such algorithms on my own, You answer is highly appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
由于某种原因无法打开此链接。我还是会尝试一下。
当您使用分而治之策略时，您所做的是将问题分解为许多较小的问题，然后将小问题的解决方案组合起来以获得主要问题的解决方案。
如何解决较小的问题：通过进一步分解它们。这个分解过程一直持续到问题小到可以直接处理为止。
如何计算时间复杂度：
假设您的算法所花费的时间是 T(n)。请注意，所花费的时间是问题大小的函数
现在，请注意您在做什么。您将问题分解为 k 个部分，每个部分的大小为 n/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)。
Can't open this link due to some reason. I'll still give it a try.
When you use the divide and conquer strategy, what you do is you break up the problem into many smaller problems and then you combine the solutions for the small problems to get the solution for the main problem.
How to solve the smaller problems: By breaking them up further. This process of breaking up continues until you reach a level where the problem is small enough to be handled directly.
How to compute time complexity:
Assume the time taken by your algo is T(n). Notice that time taken is a function of the problem size i.e. n.
Now, notice what you are doing. You break up the problems into let's say k parts each of size n/k (they may not be equal in size, in which case you'll have to add the time taken by them individually). Now, you'll solve these k parts. Time taken by each part would be T(n/k) because the problem size is reduced to n/k now. And you are solving k of these. So, it takes k * T(n/k) time.
After solving these smaller problems, you'll combine their solutions. This will also take some time. And that time will be a function of your problem size again. (It could also be constant). Let that time be O(f(n)).
So, total time taken by your algorithm will be:
T(n) = (k * T(n/k)) + O(f(n))
You've got a recurrence relation now which you can solve to get T(n).
正如此链接所示：
对于
T(2)，它是返回之前进行单次比较的基础。对于T(1)它是一个没有任何比较的基础。对于
T(n)：您递归地调用数组的两半的方法，并比较两个 (min,max) 元组以找到真正的最小值和最大值，这将为您提供上面的T(n)方程这很好地解释了它自己。
在这里，您可以通过归纳法来解决它：
基本情况：对于 n=2：
T(2) = 1 = (3/2)*2 -2我们假设对于每个
kT(k) = (3/2)k - 2nT(n) = 2T(n/2) + 2 = (*) 2*((3/2*(n/2)) -2) + 2 = 3*(n/2) -4 + 2 = (3/2)*n -2(*)归纳假设为真，因为
n/2n/2n/2n/2n/2n/2n因为我们证明了归纳法的正确性，所以我们可以得出结论：
T(n) = (3/2)n - 2As this link indicate:
for
T(2), it is a base with single comparison before returning. forT(1)it is a base without any comparison.For
T(n): You recursively call the method for two halves of the array, and compare the two (min,max) tuples to find the real min and max, which gives you the aboveT(n)equationThis is well explaining itself.
In here, you solve it with induction:
Base case: for n=2:
T(2) = 1 = (3/2)*2 -2We assume
T(k) = (3/2)k - 2for eachk < nT(n) = 2T(n/2) + 2 = (*) 2*((3/2*(n/2)) -2) + 2 = 3*(n/2) -4 + 2 = (3/2)*n -2(*)induction assumption, is true because
n/2 < nBecause we proved the induction correct, we can conclude:
T(n) = (3/2)n - 2