【正确答案】 B

【答案解析】[解析] 递推关系式T(n)=2T(n/2)+n其实是在给n个元素进行快速排序时最好情况(每次分割都恰好将记录分为两个长度相等的子序列)下的时间递推关系式，其中T(n/2)是一个子表需要的处理时间，n为当次分割需要的时间。注意，这里实际上是用比较次数来度量时间。可以对此表达式进行变形得 [*] 用n/2代替上式中的n可得 [*] 继续用n/2代替上式中的n可得 [*] 算法共需要进行[lbn]+1次分割(n个元素的序列的对半分割树的高度跟具有n个结点的完全二叉树高度相等，软设级别的只需知道即可，不必深究)，将上述[lbn]+1个式子相加，删除相互抵消的部分得 [*] 而T(1)=1，那么上式可转化为 T(n)=n[lbn]+2n 而在求时间复杂度时关注“大头”，注意到O(n)＜O(nlbn)而且对数的底可省略或为任意常数值，那么 T(n)=O(nlogn)=O(nlgn) 数学上，一般将底为10的对数简略写成lgn。