基于比较操作的排序问题的时间复杂度下界

基于比较操作的排序算法的实现过程都可以用一颗二叉树进行描述,其中非叶子节点表示一次比较操作,而比较之后的两种情况就可以用左右子树进行描述,叶子节点表示每种排序的结果。

默认根节点的高度为0,而下面每个节点的高度为根节点的高度加上根节点到该节点的路径长度。

举一个例子,两个元素 \(a,b\) 进行排序,那么只需要一次比较就可以了,所以根节点就是那一次比较操作,左叶子节点就是\(a<b\),右叶子节点就是\(a>=b\)。这棵树的高度为h=1,比较次数也为1

因此排序算法构造出来的排序树的高度,就可以反映出一个排序算法的比较次数。

我们考虑最坏的情况,假设对n个元素进行排序,那么n个元素的排列方式一共有n!种,即对应到排序树种一共有n!个叶子节点,有n!个叶子节点的二叉树的高度至少为\(log_2n!\)(满二叉树/完全二叉树),向上取整。

因为一些劣质的排序算法,可能做了很多无用的比较操作,导致非叶子节点的数量过多,或者叶子节点的数目超过n!,出现重复等,导致排序树的高度远大于 \(log_2n!\) ,那么我们可以说这个排序算法不够好。

证明基于比较操作的排序算法的时间复杂度的下界(最好的情况不能低于这个值)是O(nlogn).

练习题:n=3是画出插入排序和归并排序的排序树,并判断这种情况下对应的排序算法是不是优的

练习题:n=5时,最好的排序算法需要几次比较?并描述这种排序算法的实现过程。

发表评论

电子邮件地址不会被公开。 必填项已用*标注