flattenの2つの亜種の漸近時間の差

Question

私はScala by Exampleの文書を読む予定であり、練習問題9.4.2に問題があります。 9.4.2は、引数として要素リストのリストを取る関数flattenを、書き込みの問題を考えてみましょう

演習：ここにテキストです。 flattenの結果は、すべての要素リストを1つのリストに連結する必要があります。このメソッドの実装は、:\です。

def flatten[A](xs: List[List[A]]): List[A] = 
    (xs :\ (Nil: List[A])) {(x, xs) => x ::: xs} 

平らの2つのバージョン間の漸近的複雑さの違いは何でしょう

((Nil: List[A]) /: xs) ((xs, x) => xs ::: x) 

で平らの本体を交換を検討してください？

実際、flattenは、スタンダードのScalaライブラリのListというオブジェクト にある他のユーザフル機能のセットとともにあらかじめ定義されています。 List.flattenを呼び出すことによって、ユーザプログラムからアクセスできます。 FlattenはListクラスのメソッドではないことに注意してください。リストのリストだけに適用されるため、一般的にはすべてのリストに適用されるわけではないので、意味がありません。

これら2つの関数の漸近時間がどのように異なるかはわかりません。私は左折と右折の意味について何か基本的なものを見逃しているからだと確信しています。ここで

は、私が説明していた文書のPDFです： http://www.scala-lang.org/docu/files/ScalaByExample.pdf

私は、一般的にこれにスカラ座に優れた導入を見つけています。連結:::の実装で

Answer 1

ルック（P.68）（答えの残りの部分はスポイラータグとmaskedで、読むためにマウスオーバー！）

証人います左の引数（結果の接頭辞になるリスト）のサイズで線形です（::）。

（複雑性分析のために）リストのリストには、固定定数k、k<nのサイズが等しい等しいサイズの小さなリストnが含まれているとします。あなたがfoldLeftを使用する場合は、計算：
f
f (... (f (f a b1) b2) ...) bn

が連結したものです。あなたはfoldRightを使用する場合：

f a1 (f a2 (... (f an b) ...))

を再びf連結のプレフィックス表記放置で。後者の場合は簡単です：毎回kの要素を追加してください（k*n cons）。

最初のケース（foldLeft）の場合、最初の連結では、リスト(f a b1)のサイズはkです。あなたはサイズ2kの(f (f a b1) b2)を形成するためにb2への第2ラウンドでそれを加えます...あなたは（k+(k+k)+(3k)+... = k*sum_{i=1}^n(i) = k*n(n+1)/2 cons）です。

（フォローの質問：？これはその機能の効率を考えている間に考慮しなければならない唯一のパラメータであるが、foldLeftがfoldRightがないという利点-not漸近complexity-を持っていない？）