最小的自由数 - 分治算法

Question

我正在阅读一本名为《函数算法设计珍珠》的书。尝试实现分治算法解决“最小自由数”问题。

minfree xs = minfrom 0 (length xs) xs

minfrom a 0 _  = a
minfrom a n xs = if m == b - a
                    then minfrom b (n-m) vs
                    else minfrom a (m)   us
    where b = a + 1 + (n `div` 2)
          (us,vs) = partition (<b) xs
          m = length us

但是这个方法的速度并没有比那种被称为“朴素”的解决方案更快。而那种方案是：

import Data.List ((\\))
minfree' = head . (\\) [0..]

我不知道为什么会出现这种情况，分治算法有什么问题，如何改进它。尝试使用BangPatterns，在元组中实现了返回第一个列表长度的版本的partition，因此消除了对m = length us的额外遍历。但是这些都没有改进。第一个方法需要超过5秒，而第二个方法在ghci上几乎瞬间完成，输入[0..9999999]。

- Dulguun Otgon

Answer 1

你的输入存在病态情况，其中head . (\\) [0..]的时间复杂度为O（N）。 这里的\\定义如下：follows：

(\\) =  foldl (flip delete)

delete x xs是一种O(N)操作，它从xs中删除第一个x。foldl (flip delete) xs ys会逐个删除ys中的所有元素，直到从xs中删除所有元素为止。

在[0..] \\ [0..9999999]中，我们总是找到要删除的下一个元素在列表头部，因此可以在线性时间内计算结果。

如果您在GHCi中输入minfree' (reverse [0..9999999])，那么需要二次时间，而且基本上永远不会完成。

另一方面，分而治之算法在反转输入时不会减慢速度。

- András Kovács

---

哦，我完全忽略了minfree适用于无序列表，但是minfree只对有序列表快速有效。 - Dulguun Otgon