数组大小n的n/logn序列排序的复杂性

Question

给定一个大小为N的数组(数组包含整数)，我希望对数组进行排序，但只对数组中log(n)的长度进行排序，因此到最后，数组将具有排序的n/logn序列(以logn每个序列的大小)。

我的思想是使用MergeSort算法，在时间复杂度最坏的情况下运行O(nlogn)。但是，由于我只是对数组中的logn长度进行排序，所以时间复杂度应该是O(log( N )*log(log(N)，因为我实际上没有遍历N的整个长度。

因此，在这种情况下，MergeSort是预先形成的，即n/logn时间。假设此操作的总体时间复杂度为(n/logn)*O(log(N)_log(log(N)，=> O(n_log(log(N)是否安全？

Answer 1

您的计算是正确的:可以在n / log n中对大小为log n的数组的O(n log(log n))块进行排序。

但是，如果您的整个数组一开始不是那么大(比如几千个元素最大)，那么log n块将非常小，在这种情况下，使用插入排序实际上比使用合并排序或快速排序之类的算法更有效。