最近配对算法的效率
在T(n) = 2T(n/2) + M(n)中，T前面的2从哪里来。 n/2 因为它是除法，而 M(n) 是线性的，但我不明白 2 是做什么用的？
In T(n) = 2T(n/2) + M(n), where does the 2 in front of T come from. n/2 because it is dividing, and M(n) is linear, but I can't figure out what the 2 is for?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
2、因为您正在对两个子集执行操作。请参阅主定理。
2, because you are performing the operation on the two subsets. See the master theorem.
递归关系类似于合并排序中的关系。时间复杂度为O(n log n)
The recurrence relation is similar to what you get in Merge Sort. The time complexity would be O(n log n)
这表示大小为 n 的问题的时间成本来自于将问题一分为二（即 T(n/2)）并解决两半问题（2 T(n/2)）加上一些修复成本（即，M(n)）。
所以，2 是因为你将问题分成两半并解决两半。
This says that the time cost of the problem of size n comes from dividing the problem in half (i.e., T(n/2)) and solving it for both halves (2 T(n/2)) plus some fix-up cost (i.e., M(n)).
So, the 2 is because you divide the problem in half and solve both halves.
2 代表您要调用重复函数的次数。
例如，如果您有一棵有 4 个子节点的树，那么您期望该值是 4。在这种情况下，您会重复两次。
The 2 represents how many times you're going to call the recurring function.
For example, if you had a tree that had 4 children, you would expect a 4 for that value. In this case, you're recurring twice.