Haskell中的复杂性分析

Question

positions2              :: (Eq a) => a -> [a] -> [Int]
positions2              = f where
    f aa aas        = filter (g aa aas) [0 .. (length aas - 1)]
    g aa aas it     = aa == aas !! it

此代码用于查找给定列表中给定元素的位置.

为了找出它的复杂性,我想到了filter一个函数g和一个列表[0..length-1].

现在,我想不出什么的复杂性positions2会(n)或会有任何环路事情,由于filter功能.

请建议是否有任何其他方法来编写更紧凑的代码,以降低复杂性.

Answer 1

• 过滤器具有O(n)复杂度.
• [0..x]具有O(n)复杂度.
• (!!)具有O(n)复杂度.

由于嵌套(!!),您的天真实现是二次的

列表在这里是懒惰的,因此过滤器和列表生成器具有组合的O(n)复杂度加上每个元素的一些常量(具有惰性,列表的生成和过滤在一次传递中有效地发生).

即生成和过滤的工作是在惰性列表上的(O(n + n*k)),而不是严格列表中的O(2*n),其中k是生成单个cons单元的成本.

但是,无论如何,使用线性索引会使这个二次方成为正方形.我注意到,在具有融合的严格向量上,由于常数j查找复杂度,或者使用日志结构化查找O(n + n*log n),这将是O(n + n*j)(线性).

Answer 2

线性复杂性

positions2 :: Eq a => a -> [a] -> [Int]
positions2 x = map fst . filter ((x==).snd) . zip [0..]

main = print $ positions2 3 [1,2,3,4,1,3,4]

(我建议你阅读并理解究竟是如何工作的)

(你的代码需要二次时间,因为(!!)需要线性时间)