0

在本书http://www.scala-lang.org/docu/files/ScalaByExample.pdf的第 2 章中，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))” 但看起来不是，因为我们两次应用过滤谓词来分区数组。在经典的命令式版本中，我们对数组使用一个循环。那么功能实现的运行时间是 O(N log (N)) 吗？

4

2 回答 2

4

filter本身有 O(n) 和 O(3n) = O(n)，因为 3 是一个常数因子。不管 n 有多大，filter 只会被调用 3 次。

编辑：过滤器被调用 3 次

于 2013-02-18T22:56:53.607 回答
2

Quicksort and many other divide-and-conquer algorithms work by doing at most O(n) work for no more than O(log(n)) passes over the data. At each step we divide the data approximately in half, so that means we do indeed have only log2(n) passes through the data (one where it's not divided, one where it's divided approximately in half, etc.).

Then you just have to check that each pass through the data takes no more than O(n) time. filter is O(n), and we filter three times; plus concat is O(n) and we do it once. Thus we do 4*O(n) work, which is O(n).

It's not the most efficient algorithm because of all the passes over the same data, but it is the right order.

于 2013-02-19T01:23:36.720 回答