use*_*866 15 sorting algorithm
假设你有一个黑盒子程序,可以(log n)^a及时从n个元素的数组中提取max 0 <= a <= 1.您正在尝试创建一个使用此子例程的最佳排序算法.
显而易见的解决方案是调用整个阵列上的子程序,交换最大值与所述最后一个元素,然后迭代地对调用子程序A[1, n-1]通过A[1, 2].
有没有比n*(log n)^a时间更快的运行算法,或者显而易见的解决方案是否最佳？
我不知道确切的答案，但这里的一些结果暗示答案可能是天真的答案：
假设我们将输入分成4份（4可以用k代替）；
对这 4 个部分中的每一个进行排序需要 n/4*(log(n/4)^a)，合并结果需要 (n/2+n/2+n) = 2n；
n/4*(log(n/4)^a) * 4 = n(logn^a)-n/4*(log4)^a,
总时间 = n(logn^a) - n/4*(log4)^a + 2n
然而，如果 a = 1，则 rhs = n(log(n)^a); 如果 a < 1，则 rhs > n(log(n)^a)。
因此，即使从现实世界的角度而不是 Big-Oh 的角度考虑，分而治之的方法也只能在 a<1 时减慢速度，而在 a=1 时没有任何好处。
不过不知道还有没有其他的技巧。希望这至少能激发一些想法！