algorithm - 使用黑盒 findmax 子程序进行排序的运行时间

Question

假设您有一个黑盒子程序可以从 (log n)^a 中的 n 个元素数组中提取最大值时间，在哪里0 <= a <= 1 .您正在尝试创建一个利用此子例程的最佳排序算法。

显而易见的解决方案是对整个数组调用子程序，将最大值与最后一个元素交换，然后在A[1, n-1] 上迭代调用子程序。通过A[1, 2] .

有没有比n*(log n)^a运行得更快的更好算法时间，还是明显的解决方案是最优的？

Answer 1

没有。按照预期，我们需要黑匣子中的 Ω(n log n) 位来对 n 项进行排序。当在大小为 k 的数组上调用时，黑盒运行 (log k)^a 步并返回大约 log k 位，速率约为 (log k)^{1 - a} 每步位。该速率上限为 (log n)^{1 - a}，因此显而易见的算法是渐近最优的。