假设你有一个黑盒子程序,可以(log n)^a及时从n个元素的数组中提取max 0 <= a <= 1.您正在尝试创建一个使用此子例程的最佳排序算法.
显而易见的解决方案是调用整个阵列上的子程序,交换最大值与所述最后一个元素,然后迭代地对调用子程序A[1, n-1]通过A[1, 2].
有没有比n*(log n)^a时间更快的运行算法,或者显而易见的解决方案是否最佳？
当所有值都在1到k的范围内时,我们能否比O(n lg n)运行时间更好地进行基于比较的算法,其中k <n.
计算排序和基数排序不是基于比较的算法,不允许使用.通过决策树分析,似乎存在k ^ n个可能的排列.有2 ^ h个叶子,因此应该可以用基于比较的排序算法解决O(n lg k)时间的问题.
请不要给出基于非比较的排序算法来解决这个问题,所有排序必须基于两个元素之间的比较.谢谢!
如果你要看一个计算第n个Fibonacci数的递归实现(根100,子99和98,孙子98,97,97和96等等),大概是什么比例的数量留下递归树中的节点总数？
100
/ \
98 97
/ \ .
96 97 .
. . .
. .
不是家庭作业,只是在学术上对此感到好奇.(是的,我意识到递归实现是计算斐波纳契数的一种可怕的方法)
如何创建一个Java程序,将"Hello World"输入Google,然后从结果页面中检索html？我不是想使用Robot类.