第1个回答 推荐于2016-07-17
根据T(n) = T(ðn) + O(n) (0 < ð <1) 则有 T(n) = O(n)
因此关键问题是怎样解决划分标准的问题, 因此产生下列线性时间找中位数的算法:
将数组a有n个元素, 划分成5个一组, 则共有[n/5]个元素, 对于每组用一般的排序找中位数,需要25次, 则总共需要O(25*[n/5]) = O(n), 然后在这些中位数中递归找其中位数需要T(n/5)次,然后以找到的中位数x来作为划分标准则显然划分时间为O(n), 再递归的划分, 显然最多有3n/4的元素小于或大于x, 则选择中位数的总复杂度为:
T(n) = O(n) + T(n/5) + T(3n/4) 有T(n) = O(n)。
因此快速排序的复杂度为T(n) = 2T(n/2) + O(n) 有:T(n) = nlogn。
但最坏情况下复杂度为O(n^2)，出现此条件的情况是N个数原来就已经按照规定要求排好序了。本回答被提问者采纳