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

这段代码是用来查找给定列表中给定元素的位置。

为了确定其复杂度，我考虑使用一个带有函数 g 和列表 [0..length-1] 的 filter。

现在，我无法确定 positions2 的复杂度是 (n) 还是由于 filter 函数而循环执行。

如果有其他方法可以编写更紧凑、复杂度更低的代码，请提出建议。

- anujuhi01

---

重复的http://stackoverflow.com/questions/6322053/haskell-program-to-find-the-position-of-an-element-in-a-list - Mark Karpov

@Mark 他在询问复杂度（但是是的，非常接近...） - josejuan

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*j)（线性的），或者通过对数结构查找，O(n+n*log n)。

- Don Stewart

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]

我建议您阅读并理解它的工作原理。

由于 (!!) 的时间复杂度为线性时间，因此您的代码需要二次时间。

- josejuan

Answer 3

首先，进行一些转换：

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
-- ==
positions2 aa aas  = filter (g aa aas) [0 .. (length aas - 1)]
    g aa aas it     = aa == aas !! it
-- ==
positions2 aa aas  = [it | it <- [0 .. (length aas - 1)], aa == (aas !! it)]
{- 
positions2 aa aas = for each it in [0 .. (length aas - 1)]
                      if (aas !! it) == aa
                        emit it
-}

现在你可以清楚地看到，对于给定的it，通过(!!)遍历列表aas是从其起始位置重新开始的，这是一种典型的二次行为，当完全探索positions2 aa aas的结果时（返回的列表被遍历到其末尾），您执行了1+2+3+4+...+n = O(n²)步骤。

但是，您正在探索逐渐增加的索引，因此您可以从列表中的前一个点（而不是从其开头）开始，并且每次仅向前移动1个位置（而不是像(!!)那样移动整个it索引）。

positions2 aa aas = g 0 aas
   where
      g i (a:as) | a == aa = i : g (i+1) as
                 | otherwise =   g (i+1) as
      g _ [] = []

在这里，您可以看到索引加1（i-->i+1）与沿着列表向前移动一个位置（(a:as)-->as）的增量是如何交织在一起的。

再次使用列表推导式，通过使用zip来实现编织（或实际上更像是压缩）。

positions2 aa aas = [it | (a,it) <- zip aas [0 .. (length aas - 1)]
                        , a == aa]
{-
    = for each a in aas while incrementing it by 1 from 0 to (length aas - 1),
        if a == aa
          emit it
-}

这现在显然是一个O(n)的解决方案。由于Haskell的列表是惰性的，而zip会在最短的列表结束时停止。

positions2 aa aas = [it | (a,it) <- zip aas [0 ..], a == aa]

（这相当于 这里的答案 中的代码。）

- Will Ness