不是VIP会员，不能显示答案

题目解答

题目：
应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（ ）。
  • A.O(n2)
  • B.O(n log n)
  • C.O(n)
  • D.O(1)
考点： 0
分析：
解答： 解析：快排的时间复杂度是O（nlogn），利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)。
评论：
老师： 0