问题：
合并k排序的阵列每个元素在最小的时间复杂性下将n元素带入一个大小NK的单个数组。该算法应是基于比较的算法。
不应在输入上进行假设。
因此，我知道在此处提到的nklogk时间复杂性解决问题的算法：。
但是，我的问题是我们可以在少于 nklogk 中排序，意思是，运行时为 o（nklogk）。
因此，我通过互联网搜索并找到了这个答案：
Merge k in o（o（o） NK）时间复杂性
声称将大小K的数组分为单例，然后将它们合并为单个数组。但这是不正确的，因为人们可以声称他找到了一种算法，该算法可以在 sqrt（n）klogk 中解决该问题，该算法是 o（nklogk） n = 1 因此，我们对 klogk 时间的数组进行排序，该数组与对数组的排序不矛盾。
那么，我该如何与分类数组的下限相抵触呢？含义，对于一个大小为n的数组，在输入上没有任何假设，排序至少需要NLOGN操作。
The question:
Merge k sorted arrays each with n elements into a single array of size nk in minimum time complexity. The algorithm should be a comparison-based algorithm. No assumption on the input should be made.
So I know about an algorithm that solves the problem in nklogk time complexity as mentioned here: https://www.geeksforgeeks.org/merge-k-sorted-arrays/.
Though, my question is can we sort in less than nklogk, meaning, the runtime is o(nklogk).
So I searched through the internet and found this answer:
Merge k sorted arrays of size n in O(nk) time complexity
Which claims to divide an array of size K into singletons and merge them into a single array. But this is incorrect since one can claim that he found an algorithm that solves the problem in sqrt(n)klogk which is o(nklogk) but n=1 so we sort the array in KlogK time which doesn't contradict the lower bound on sorting an array.
So how can I contradict the lower bound on sorting an array? meaning, for an array of size N which doesn't have any assumptions on the input, sorting will take at least NlogN operations.
发布评论
评论（1）
n log n的下限仅适用于基于比较的排序算法（堆排序，合并排序等）。当然，有一些分类算法具有更好的时间复杂性（例如计数排序）但是，它们不是基于比较的。The lower bound of
n log nonly applies to comparison-based sorting algorithms (heap sort, merge sort, etc.). There are, of course, sorting algorithms that have better time complexities (such as counting sort), however they are not comparison-based.