时间复杂度Log(n)的排序算法

Question

有没有平均时间复杂度log(n)的排序算法？

示例 [8,2,7,5,0,1] 以时间复杂度 log(n) 对给定数组进行排序

Answer 1

不; 事实上，这对于任意列表来说是不可能的！我们可以相当简单地证明这一点：对于排序我们必须做的绝对最少的事情是至少查看列表中的每个元素一次。毕竟，一个元素可能属于排序列表中的任何位置；如果我们不看某个元素，就不可能对数组进行排序。这意味着任何排序算法的下界都是n，并且由于n > log(n)，log(n)排序是不可能的。

尽管n是下界，但大多数排序（如合并排序、快速排序）都是n*log(n)时间。事实上，虽然n在某些情况下我们可以使用基数排序对纯数字列表进行及时排序，但我们实际上无法对任意对象（例如小于 的字符串）进行排序n*log(n)。

也就是说，有时该列表可能不是任意的；前任。我们有一个除了一个元素之外完全排序的列表，我们需要将该元素放入列表中。在这种情况下，像二叉搜索树这样的方法可以让您插入 in log(n)，但这只是可能的，因为我们正在操作单个元素。构建一棵树（即执行n插入）是n*log(n)时间。