这是一个创建于 2598 天前的主题，其中的信息可能已经有所发展或是发生改变。
递归深度 depth 是 logn，每个节点的数据处理的时间复杂度是 O(n)，所以每层数据处理的时间复杂度是 O(n)，然后每层的 O(n)*depth，即归并排序的时间复杂度为 O(nlogn)。
 |
1
lsmgeb89 2018 年 12 月 23 日
每个节点并不是 O(n)
但每层是 O(n) 那空间复杂度呢？ |
 |
2
geelaw 2018 年 12 月 23 日 via iPhone
可以这样考虑。
|
|
4
lsmgeb89 2018 年 12 月 23 日
硬要说 O(n) 也没错。
辅助数组看你代码怎么写了，不同的代码分析略有不同。 |
 |
5
maggch 2018 年 12 月 23 日
T(n) = 2 T(n/2) + n
|
 |
6
exonuclease 2018 年 12 月 24 日 via iPhone
可以求解递归式或者用递归树
|
 |
7
king0101 2018 年 12 月 24 日
我一直也是这样理解的
|
Select Language