首页 > 解决方案 > 一个大小为 n 的数组,具有 n/logn 个序列号,每个序列都是 logn 长且有序

问题描述

使用合并算法将前两个序列合并,然后将第三个序列与新的序列合并,依此类推。

这个算法的时间和空间复杂度是多少?

知道合并算法是 O(n),我们必须循环它 (n/logn)-1) 次,所以时间复杂度是 O(n*(n/logn)-1))?

对于空间复杂度,每次我们使用大小为 k*logn 的临时数组循环 (n/logn)-1) 次,所以空间复杂度为 O((n/logn)-1)logn)?

标签: time-complexity

解决方案


推荐阅读