随机快速排序的期望代价 快速排序的主要代价其实就是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的代价主要是循环中的比较操作
为什么： Our goal,therefore,is to compute X,the total number of comparisons performed in all calls to PARTITION.We will not attempt to analyze how many comparisons are made in each call to PARTITION
为什么： Our goal, therefore, is to compute X, the total number of comparisons performed in all calls to PARTITION. We will not attempt to analyze how many comparisons are made in each call to PARTITION