请教，我这么理解递归实现的归并排序(MergeSort)的时间复杂度,对吗？

2018 年 12 月 23 日
 NotreDame
递归深度 depth 是 logn，每个节点的数据处理的时间复杂度是 O(n)，所以每层数据处理的时间复杂度是 O(n)，然后每层的 O(n)*depth，即归并排序的时间复杂度为 O(nlogn)。
3211 次点击
所在节点    问与答
7 条回复
lsmgeb89
2018 年 12 月 23 日
每个节点并不是 O(n)

但每层是 O(n)

那空间复杂度呢？
geelaw
2018 年 12 月 23 日
可以这样考虑。
NotreDame
2018 年 12 月 23 日
@lsmgeb89 节点不是 O(n)吗？ 空间复杂度是辅助数组的空间 O(n)。
lsmgeb89
2018 年 12 月 23 日
硬要说 O(n) 也没错。

辅助数组看你代码怎么写了，不同的代码分析略有不同。
maggch
2018 年 12 月 23 日
T(n) = 2 T(n/2) + n
exonuclease
2018 年 12 月 24 日
可以求解递归式或者用递归树
king0101
2018 年 12 月 24 日
我一直也是这样理解的

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://v2ex.ih06.com/t/520167

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX