http://i.imgur.com/cmfwn1S.jpg
因为在解释里好像没特别说是用什么样的sorting方式，其他算法大多是用comparison ba
se
还有T(n)=T(n/5)+T(3n/4)+O(n)→→→这个O(n)是哪来的QQ

他又不是做sortingO(n)是1.2.4步的时间5个数排列 就算用初等排序 也才5^2=25是一个常数 然后又有n/5组 所以那一步还是花n的时间递回求中位数的中位数那只是把一堆中位数再丢下去递回 所以时间就是T(n/5)而且递回也不是排列中位数 而只是要找中位数的中位数 所以递回下去也只是要找那n/5个数中的第n/2大的数而已1.2.4各花n 加起来还是n 所以他就省略了

Sort o(n)是因为每堆只有5个 假设采n log n的sorting 也才5log5 是常数 因为有n/5堆 所以总共是nlog5 是O(n)

那个O(n)你用第四步骤看 全部的数跟P比大小分堆 至少要比较n次

可以google median of median 网络上有很多讲解～