Pearls

Pearl 2: 给定一个长度大于1的列表, 计算其元素的最大surpasser count, 要求算法复杂度 $O(n log n)$. Type: msc: Ord a => [a] -> Int “Pearls of functional algorithm design"的第二章, 我们先来看surpasser的定义 Definition surpasser: 称列表中$X[j]$是$X[i]$的surpasser, 如果$X[i] < X[j]$且$i < j$. 因此一个元素的surpasser count就是其surpasser的数目. 同样, 一个naive的实现很容易: 1 2 3 4 msc :: Ord a => [a] -> Int msc xs = maximum [scount z zs | z:zs <- tails xs] scount :: Ord a => a -> [a] -> Int scount x xs = length $ filter (> x) xs 同时也很容易看到, 这个实现的时间复杂度是 $O(n^2)$, 不符合要求的 $O(n log n)$. 为了达到 $O(n log n)$ 的时间复杂度, 我们希望有个函数f能够递归的处理xs = us ++ vs, 并且存在一个线性复杂度的函数join, 使得f xs = join (f us) (f vs), 这样整体的复杂度满足 $T(n)=2 T(n/2)+O(n)=O(n log n)$. 原文中, 作者利用分治的思想通过一步步地推导获得了线性时间的join, 这里也仅仅是类似于复读的"再解释”. ...

Pearl 1: 给定一个自然数的有限集X, 计算不属于X的最小自然数. X表示为不包含重复元素的无序列表. 时间复杂度要求$O(n)$. Type: minfree :: [Int] -> Int(也可以额外的定义自然数类型, 不过这不是我们的重点) “Pearls of Functional Algorithm Design"的第一章, 其描述了一个分治的算法和一个基于array的算法, 这里按个人的思路讲解一下基于分治的算法, 基于array的算法具体可以查阅原文. 首先拿到这个问题, 我觉得最直接的想法就是 Base Solution: minfree xs = head $ [0..] \\ xs 然而这和要求的线性时间复杂度不符. 第二个想法就是设计一个fold的函数遍历一遍列表, 这样时间复杂度符合要求. 但是越来越多的边界条件让我意识到思路不对. 看了原文才发现忽略了解题的一个重要条件. Fact: [0..n]中的所有自然数不可能都在X(xs)中, 其中n = length xs. 这也很容易证明, 因为$ n + 1 = length\ [0..n] > n $, 因此不属于集合X的最小自然数就是[0..n]中不属于X的最小自然数. 至此,该问题很容易解决, 只需要一个marked的array来表示[0,,n]中的自然数是否在X中即可. 下面描述基于分治的算法, 首先给出一个基本的结论. Theorem: (as ++ bs) \\ (us ++ vs) == (as \\ us) ++ (bs \\ vs), 如果as \\ vs == as && bs \\ us == bs. ...