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

This topic created in 2875 days ago, the information mentioned may be changed or developed.

递归深度 depth 是 logn，每个节点的数据处理的时间复杂度是 O(n)，所以每层数据处理的时间复杂度是 O(n)，然后每层的 O(n)*depth，即归并排序的时间复杂度为 O(nlogn)。

7 replies • 2018-12-24 11:32:15 +08:00

lsmgeb89

Dec 23, 2018

每个节点并不是 O(n)

但每层是 O(n)

那空间复杂度呢？

geelaw

Dec 23, 2018 via iPhone

可以这样考虑。

NotreDame

Dec 23, 2018

@lsmgeb89 节点不是 O(n)吗？空间复杂度是辅助数组的空间 O(n)。

lsmgeb89

Dec 23, 2018

硬要说 O(n) 也没错。

辅助数组看你代码怎么写了，不同的代码分析略有不同。

maggch

Dec 23, 2018

T(n) = 2 T(n/2) + n

exonuclease

Dec 24, 2018 via iPhone

可以求解递归式或者用递归树

king0101

Dec 24, 2018

我一直也是这样理解的