登机门|登机门CS 2008 |问题43

考虑快速排序算法。假设有一个查找轴心元素的过程，它将列表拆分为两个子列表，每个子列表至少包含五分之一的元素。设T（n）为对n个元素进行排序所需的比较次数。然后

（A） T（n）<=2T（n/5）+n （B） T（n）<=T（n/5）+T（4n/5）+n （C） T（n）<=2T（4n/5）+n （D） T（n）<=2T（n/2）+n 答复: （B） 说明： 对于n/5个元素位于一个子集中的情况，第一个子集需要与n/5个元素进行T（n/5）比较，T（4n/5）表示其余4n/5个元素，n表示查找轴心。

如果一个集合中有超过n/5个元素，那么另一个集合将有少于4n/5个元素，时间复杂度将小于T（n/5）+T（4n/5）+n，因为递归树将更加平衡。 这个问题的小测验