algorithm - 最近对算法的效率

Question

在T(n) = 2T(n/2) + M(n)中，T前面的2从何而来。n/2 因为它是除法，而 M(n) 是线性的，但我不知道 2 是干什么用的？

score 4 · Accepted Answer

4

2，因为你正在对两个子集执行操作。见主定理。

于 2011-04-25T16:12:21.310 回答

score 1 · Accepted Answer

这表示大小为 n 的问题的时间成本来自于将问题分成两半（即 T(n/2)）并将其解决为两半（2 T(n/2)）加上一些修复成本(即，M(n))。

因此，2 是因为您将问题分成两半并解决两半。

score 1 · Accepted Answer

2 表示您将调用循环函数的次数。

例如，如果您有一棵有 4 个孩子的树，您会期望该值为 4。在这种情况下，您会重复两次。

score 1 · Accepted Answer

1

递归关系类似于您在Merge Sort中得到的关系。时间复杂度为O(n log n)

于 2011-04-25T16:09:44.567 回答

4 回答 4