随机快速排序的期望代价 快速排序的主要代价其实就是Partition的代价。 ■Partition的代价主要是循环中的比较操作。 Lemma 7.1 Let X be the number of comparisons performed in line 4 of PARTITION over the entire execution of QUICKSORT on an n-element array.Then the running time of QUICKSORT is O(n+X). Proof By the discussion above,the algorithm makes at most n calls to PARTI- TION,each of which does a constant amount of work and then executes the for loop some number of times.Each iteration of the for loop executes line 4.随机快速排序的期望代价 ◼ 快速排序的主要代价其实就是Partition的代价。 ◼ Partition的代价主要是循环中的比较操作