haskell - 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)(线性)。