在最后一个元素上选择随机枢轴以进行快速选择有什么意义吗？
我仍然可以通过始终选择最后一个元素作为枢轴来找到所需的元素。它会影响运行时。
问问题
1028 次
1 回答
3
枢轴的选择对给定数组上快速选择的运行时间有巨大影响。
在确定性快速选择中，如果您总是选择最后一个元素作为枢轴，想象一下如果您尝试从始终排序的列表中选择会发生什么。您的枢轴将始终是最差的枢轴，并且只会从数组中消除一个数字，从而导致 Θ(n 2 ) 运行时。
在随机快速选择中，如果算法在每次递归调用中总是做出最坏的选择，那么运行时仍然可能是 Θ(n 2 )，但这极不可能。运行时间很可能是 O(n)，并且没有“杀手”输入。
换句话说，带有确定性选择枢轴的快速选择将始终具有至少一个“杀手”输入，迫使它在时间 Θ(n 2 ) 中运行，而带有随机枢轴的快速选择没有杀手输入并且具有出色的平均时间保证. 结果，分析完全不同。
希望这可以帮助！
于 2015-01-28T21:40:13.697 回答