0

本の第2章http://www.scala-lang.org/docu/files/ScalaByExample.pdfで、M。Oderskyはクイックソートの次の実装を書いています

def sort(xs: Array[Int]): Array[Int] = {
 if (xs.length <= 1) xs
 else {
 val pivot = xs(xs.length / 2)
  Array.concat(
   sort(xs filter (pivot >)),
   xs filter (pivot ==),
   sort(xs filter (pivot <)))
 }
}

そして、「命令型と機能型の両方の実装は、同じ漸近的な複雑さを持っています–平均的な場合はO（N log（N））」と言いましたが、配列を分割するためにフィルター述語を2回適用するため、そうではないようです。従来の命令バージョンでは、配列に1つのループを使用しています。では、機能実装の実行時間はO（N log（N））ですか？

4

2 に答える 2

4

filter3は定数係数であるため、それ自体はO（n）およびO（3n）= O（n）になります。nがいくら大きくても、フィルターは3回しか呼び出されません。

編集：フィルターは3回呼び出されます

于 2013-02-18T22:56:53.607 に答える
2

クイックソートおよび他の多くの分割統治アルゴリズムO(n)は、多くてもO(log(n))データを渡すだけで機能します。各ステップでデータを約半分に分割します。つまり、実際にはlog2(n)データを通過するだけです（分割されていないデータ、約半分に分割されているデータなど）。

次に、データを通過するたびに時間がかからないことを確認する必要がありますO(n)。filterはO(n)、であり、3回フィルタリングします。プラスconcatはそうですO(n)、そして私たちは一度それをします。したがって、私たちは4*O(n)仕事をします、それはO(n)です。

すべてのパスが同じデータを通過するため、これは最も効率的なアルゴリズムではありませんが、正しい順序です。

于 2013-02-19T01:23:36.720 に答える