你的浏览器禁用了JavaScript, 请开启后刷新浏览器获得更好的体验!

最接近对算法的效率

| 在T（n）= 2T（n / 2）+ M（n）中，T前面的2从何而来。 n / 2，因为它是相除的，并且M（n）是线性的，但是我不知道2的含义是什么？

已邀请:

4 个回复

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

重复关系类似于您在“合并排序”中获得的关系。时间复杂度为O（n log n）

这就是说，大小为n的问题的时间成本来自将问题分为两半（即T（n / 2）），并求解为两半（2 T（n / 2））加上一些固定成本（即M（n））。所以2是因为您将问题分为两半，并且两半都解决了。

2代表您要调用重复功能的次数。例如，如果您的树上有4个孩子，则该值应为4。在这种情况下，您要重复两次。

要回复问题请先登录或注册