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

このコードは、指定されたリスト内の指定された要素の位置を見つけるためのものです。

その複雑さを知るために、私は関数とリストfilterを取ることを考えました。g[0..length-1]

今、私はの複雑さが何であるか、または機能のためにループが発生positions2するかどうかを理解できません。(n)filter

これよりも複雑さを軽減するために、よりコンパクトなコードを記述する他の方法があるかどうかを提案してください。

4

3 に答える 3

9
  • フィルターの複雑さはO(n)です。
  • [0..x] の複雑さはO(n)です。
  • (!!)O(n)の複雑さがあります。

ネストされているため、単純な実装は二次です（!!）

ここではリストが遅延しているため、フィルターとリスト ジェネレーターはO(n)の複雑さと要素ごとの定数を組み合わせています (遅延により、リストの生成とフィルター処理は 1 つのパスで効果的に行われます)。

つまり、生成とフィルタリングの作業は、厳密なリストのO(2*n)ではなく、遅延リストの(O(n+n*k))です。ここで、 kは単一のコンス セルを生成するコストです。

ただし、線形インデックスを使用すると、とにかくこれが二次になります。フュージョンを使用した厳密なベクトルでは、定数jのルックアップの複雑さ、または対数構造のルックアップO(n+n*log n)により、これはO(n+n*j) (線形) になることに注意してください。

于 2014-10-06T10:18:14.433 に答える
5

線形の複雑さ

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]

（正確にどのように機能するかを読んで理解することをお勧めします）

（あなたのコードは(!!)線形時間を取るので二次時間かかります）

于 2014-10-06T09:35:18.523 に答える
1

まず、いくつかの変換:

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繰り返されることがはっきりとわかります(!!)。これは古典的な 2 次動作です。の結果が完全に探索されるまでに1+2+3+4+...+n = O(n 2 )positions2 aa aasステップを実行します(返されたリストは最後までトラバースされます)。 .

ただし、徐々に増加するインデックスを探索するため、リストに沿って ( start からではなく) 前のポイントから開始し、毎回 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 ずつの増分 ( ) と、リストに沿った 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]

(これは、こちらの回答のコードと同等です)。

于 2014-10-07T08:11:38.773 に答える