Question

以下哪个排序算法的最坏时间复杂度是O(nlogn)?

Answer 1

这个首先要明确一点，只用到比较的排序算法最低时间复杂度是O(nlogn)，而像桶排这样的只需要O(R)(R为桶的大小)。

为了证明只用到比较的排序算法最低时间复杂度是O(nlogn)，首先要引入决策树。

首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。

先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。

具有L片树叶的二叉树的深度至少是logL。

所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。