给定一个大小为n的数组,它被分成了n/k个大小为k的区间。每个区间中的值都比其左侧的区间大,比其右侧的区间小。我想在最短的时间内对这些值进行排序。
我想到的朴素解决方案是仅对每个区间中的所有值进行排序,这将“花费”O(k log k)的时间,对于所有n/k个区间的总成本为O(n log k)。我想知道是否有更有效的方法。
现在我知道每个区间中最多只有log log k个不同的值,我需要想出一种更快的算法。希望您能帮助我。
谢谢!
我想到的朴素解决方案是仅对每个区间中的所有值进行排序,这将“花费”O(k log k)的时间,对于所有n/k个区间的总成本为O(n log k)。我想知道是否有更有效的方法。
现在我知道每个区间中最多只有log log k个不同的值,我需要想出一种更快的算法。希望您能帮助我。
谢谢!
n * X
降低到g(n) * X
,因此我认为您不能减少n
。 - Saeed Amirin\k
是指n/k
,也就是“n除以k”吗? - Svante