伪快速排序时间复杂度

Question

我知道quicksort的O(n log n)平均时间复杂度.伪快速排序(当你从足够远的地方看它,具有适当高的抽象级别时只是一个快速排序),通常用于演示函数语言的简洁性如下(在Haskell中给出):

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]

好的,所以我知道这件事有问题.最大的问题是它没有排序,这通常是quicksort的一大优势.即使这没关系,它仍然需要比典型的快速排序更长的时间,因为它在分区时必须进行两次列表传递,然后它会进行昂贵的附加操作以将其拼接回来.此外,选择第一个元素作为枢轴不是最佳选择.

但即便考虑所有这些,这个快速排序的平均时间复杂度与标准快速排序不同吗？即,O(n log n)？因为追加和分区仍然具有线性时间复杂度,即使它们效率低下.

Answer 1

这种"快速排序",实际上是砍伐树排序: http://www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell

data Tree a = Leaf | Node a (Tree a) (Tree a)

mkTree [] = Leaf
mkTree (x:xs) = Node x (mkTree (filter (<= x) xs)) (mkTree (filter (x <) xs))

二叉树是不平衡的,因此建立搜索树的O(N ^ 2)最坏情况和O(N*Log N)平均情况复杂度.

foldTree f g Leaf = g
foldTree f g (Node x l r) = f x (foldTree f g l) (foldTree f g r)

treeSort l = foldTree (\x lft rht -> lft++[x]++rht) [] (mkTree l)

检索算法具有O(N ^ 2)最坏情况和O(N*Log N)平均情况复杂度.

良好的平衡:

Prelude> let rnds = iterate step where step x = (75*x) `mod` 65537
Prelude> length . quicksort . take 4000 . rnds $ 1
4000
(0.08 secs, 10859016 bytes)
Prelude> length . quicksort . take 8000 . rnds $ 1
8000
(0.12 secs, 21183208 bytes)
Prelude> length . quicksort . take 16000 . rnds $ 1
16000
(0.25 secs, 42322744 bytes)

不那么均衡:

Prelude> length . quicksort . map (`mod` 10) $ [1..4000]
4000
(0.62 secs, 65024528 bytes)
Prelude> length . quicksort . map (`mod` 10) $ [1..8000]
8000
(2.45 secs, 241906856 bytes)
Prelude> length . quicksort . map (`mod` 10) $ [1..16000]
16000
(9.52 secs, 941667704 bytes)

Answer 2

我同意你的假设，即平均时间复杂度仍然是O(n log n)。我不是专家，也不是 100% 确定，但这些是我的想法：

这是就地快速排序的伪代码：（使用 l=1 和 r=数组长度调用快速排序）

Quicksort(l,r)  
--------------
IF r-l>=1 THEN  
    choose pivot element x of {x_l,x_l+1,...,x_r-1,x_r}   
    order the array-segment x_l,...x_r in such a way that  
        all elements < x are on the left side of x // line 6  
        all elements > x are on the right side of x // line 7  
    let m be the position of x in the 'sorted' array (as said in the two lines above)  
    Quicksort(l,m-1);  
    Quicksort(m+1,r)  
FI  

然后，平均时间复杂度分析通过选择第 6 行和第 7 行中的“<”比较作为该算法的主导操作进行推理，最终得出平均时间复杂度为 O(n log n) 的结论。由于不考虑“以...的方式对数组段 x_l,...x_r 进行排序”行的成本（如果您想找到边界，则在时间复杂度分析中只有主导操作很重要），我认为“因为它在对列表进行分区时必须对列表进行两次遍历”不是问题，而且您的 Haskell 版本在此步骤中只需要大约两倍的时间。对于附录操作也是如此，我同意这不会增加渐近成本：

因为追加和分区仍然具有线性时间复杂度，即使它们效率低下。

为了方便起见，我们假设这将“n”添加到我们的时间复杂度成本中，因此我们有“O(n log n+n)”。由于存在一个自然数 o，且 n log n > n 对于所有大于 o 的自然数都成立，因此您可以将 n log n +n 估计到顶部 2 n log n 并估计到底部 n log n，因此n log n+n = O(n log n)。

此外，选择第一个元素作为枢轴并不是最佳选择。

我认为主元元素的选择在这里无关紧要，因为在平均情况分析中，您假设数组中元素均匀分布。您无法知道应该从数组中的哪个位置选择它，因此您必须考虑所有这些情况，其中您的枢轴元素（独立于您从列表的哪个位置获取它）是第 i 个最小元素你的列表中，i=1...r。