伪快速排序时间复杂度 [英] Pseudo-quicksort time complexity

问题描述

我知道quicksort的平均时间复杂度为 O（n log n）。一个伪快速排序（它只是一个快速排序，当你从足够远的地方看到它时，具有适当高的抽象级别）常常用于演示函数式语言的简洁性如下（在Haskell中给出）： p>

  quicksort :: Ord a => [a]  - > [a] 
 quicksort [] = [] 
 quicksort（p：xs）= quicksort [y | y< -xs，y< p] ++ [p] ++ quicksort [y | y< -xs，y> = p] 
  

好的，所以我知道这个东西有问题。这个问题最大的问题是它不能排序，这通常是快速排序的一大优势。即使这并不重要，它仍然需要比典型的快速排序更长的时间，因为它在分区时必须执行两次列表扫描，而且它会执行昂贵的附加操作，以便将其重新拼接在一起。此外，选择第一个元素作为关键点并不是最佳选择。

但即使考虑到所有这些，也不是这个quicksort的平均 time 复杂度与标准quicksort相同吗？即， O（n log n）？因为追加和分区仍然具有线性时间复杂性，即使它们效率低下也是如此。

解决方案

这个quicksort实际上被砍伐了树排序：
http://www.reddit.com/r/编程/评论/ 2h0j2 / real_quicksort_in_haskell

 数据树a = Leaf |节点a（树a）（树a）
 
 mkTree [] =叶
 mkTree（x：xs）=节点x（mkTree（filter（<= x）xs））（ mkTree（filter（x <）xs））
  

二叉树不平衡，所以O（N ^ 2）最差情况和O（N * Log N）建筑搜索树的平均情况复杂度。

  foldTree fg Leaf = g 
 foldTree fg（Node xlr）= fx（foldTree fgl）（foldTree fgr）
 
 treeSort l = foldTree（\ x lft rht  - > lft ++ [x] ++ rht） []（mkTree l）
  

检索算法有O（N ^ 2）最差情况和O N * Log N）平均情况下的复杂性。

平衡：

 前奏>让rnds =迭代步骤，其中步骤x =（75 * x）`mod` 65537 
 Prelude>长度 。快速排序。拿4000。 rnds $ 1 
 4000 
（0.08秒，10859016字节）
前奏>长度 。快速排序。采取8000。 rnds $ 1 
 8000 
（0.12秒，21183208字节）
前奏>长度 。快速排序。取16000。 rnds $ 1 
 16000 
（0.25秒，42322744字节）
  

如此平衡：

  Prelude>长度 。快速排序。 map（`mod` 10）$ [1..4000] 
 4000 
（0.62秒，65024528字节）
 Prelude>长度 。快速排序。 map（`mod` 10）$ [1..8000] 
 8000 
（2.45秒，241906856字节）
 Prelude>长度 。快速排序。 map（`mod` 10）$ [1..16000] 
 16000 
（9.52秒，941667704字节）
  

I know that quicksort has O(n log n) average time complexity. A pseudo-quicksort (which is only a quicksort when you look at it from far enough away, with a suitably high level of abstraction) that is often used to demonstrate the conciseness of functional languages is as follows (given in Haskell):

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

Okay, so I know this thing has problems. The biggest problem with this is that it does not sort in place, which is normally a big advantage of quicksort. Even if that didn't matter, it would still take longer than a typical quicksort because it has to do two passes of the list when it partitions it, and it does costly append operations to splice it back together afterwards. Further, the choice of the first element as the pivot is not the best choice.

But even considering all of that, isn't the average time complexity of this quicksort the same as the standard quicksort? Namely, O(n log n)? Because the appends and the partition still have linear time complexity, even if they are inefficient.

解决方案

This "quicksort" is actually deforested tree sort: 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))

Binary tree is unbalanced, so O(N^2) worst-case and O(N*Log N) average-case complexity for building search tree.

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)

Retrieval algorithm have O(N^2) worst-case and O(N*Log N) average-case complexity.

Well-balanced:

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)

Not-so-well-balanced:

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)

这篇关于伪快速排序时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！