首页 > 试题广场 >

在寻找 n 个元素中第 k 小元素问题中,如

[单选题]

在寻找 n 个元素中第 k 小元素问题中,如使用快速排序算法思想,运用分治算法对 n 个元素进行划分,应如何选择划分基准?下面( ) 答案解释最合理。

  • 随机选择一个元素作为划分基准
  • 取子序列的第一个元素作为划分基准
  • 用中位数的中位数方法寻找划分基准
  • 以上皆可行。但不同方法,算法复杂度上界可能不同
所以,时间复杂度的上界是最坏情况?三种的最坏情况都是O(n2)吧,只是相对来说概率不同,但并不影响最坏情况的出现呀。
编辑于 2018-03-09 09:05:31 回复(0)
AB的上界是O(n^2),C的上界是O(n),所以推荐使用C方法
发表于 2018-09-01 15:40:00 回复(0)
AB不用说,C是BFPRT算法的精髓,是n 个元素中第 k 小元素问题的最优解决方法
发表于 2017-09-05 15:51:48 回复(0)