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