5

我想出了一个解决另一个 SO问题的想法，并希望在确定函数的复杂性方面得到一些帮助，因为我对此不太了解。我猜测“未分类”每个块会是正确的吗？那么将一个块的最后一个块与另一个块的头部进行比较的 sortBy 函数的复杂性是多少？我的猜测是该函数只会比较对，而不需要根据总列表查找一个块的顺序。此外，Haskell 是否会因为整体功能的延迟优化而提供不同的复杂性？提前致谢！O (n * log 2)

import Data.List.Split (chunksOf)
import Data.List (sortBy)

rearrange :: [Int] -> [Int]
rearrange = concat 
          . sortBy (\a b -> compare (last a) (head b)) 
          . map (sortBy (\a b -> compare b a)) 
          . chunksOf 2
4

2 回答 2

5

好一步一步

  1. chunksOf 2必须遍历整个列表，所以O(n)我们是列表长度的一半。然而，由于常数倍数不会影响复杂性，我们可以忽略这一点。
  2. map (sortBy...遍历整个列表O(n)进行恒定时间操作* O(1)= O(1*n)=O(n)
  3. sortBy具有恒定时间比较*是O( n * log n)
  4. concat这是O(n)

所以总共O(n + n + n log n + n)= O ((3 + log n) * n)=O(n log n)

*由于列表的长度保证为 2 或更少，我们可以说排序和访问最后一个元素等操作分别是O(2 * log 2)和O(2)，它们都是常数时间，O(1)

于 2013-05-26T15:47:13.880 回答
5

让我们单独看一下各个部分（让我们n成为列表参数的长度）：

  • chunksOf 2是O(n)，产生一个长度列表(n+1) `quot` 2。
  • map (sortBy ...)：由于所有传递给的列表都sortBy ...具有 length <= 2，因此这些排序中的每一个都是O(1)，因此整个列表又map是O(n)。
  • sortBy (\a b -> compare (last a) (head b)): 比较总是O(1)，因为last被取元素的列表是有界长度 ( <= 2)，因此整个sortBy操作是O(n*log n)
  • concat又是O(n)。

所以总的来说，我们有O(n*log n)。

但是请注意，

cmp = \a b -> compare (last a) (head b)

是一个不一致的比较，对于两个列表a和b（比如说[30,10]和[25,15]），你可以有

cmp a b == cmp b a = LT

我不确定您的算法是否总是有效。

在我的脑海中查看了排序的实现sortBy和跟踪之后，我认为对于给定的目的，它可以工作（假设列表元素是不同的）并且不一致的比较没有害处。对于某些排序算法，不一致的比较可能会导致排序循环，但对于合并排序变体，不应该发生这种情况。

于 2013-05-26T15:47:42.707 回答