我的排列函数编码 scala 上的大 O-Notation

Question

以下代码是列表中元素置换的实现，由scala编码

def permute(list:List[Int]):List[List[Int]] =
  if(list.isEmpty) {
    Nil
  } else {
    var result: List[List[Int]] = Nil

    def recursion(plist: List[Int], rlist: List[Int]): Unit = {
      if (rlist.isEmpty)
        result ++= plist :: Nil

      if (plist != list.reverse)
        for (i <- rlist.indices) {
          val x = rlist(i)
          val xDropped = drop(x, rlist)
          val newPList = plist ++ (x :: Nil)
          recursion(plist ++ (x :: Nil), xDropped)
        }
    }

    recursion(Nil, list)
    result
  }

def drop(x:Int, list:List[Int]) = list.filter(_ != x)
val result = permute(xs)
result.foreach(println)
println(result.length)

控制台将显示如下。

console result 我关心的是这个函数的大 O 符号是什么，以及如何计算？

我希望你详细描述产生大 O 符号的方法

谢谢，祝你有愉快的一天。

Answer 1

好吧，你的算法太复杂了，因为有很多次优步骤。 Scala API 乍一看是势不可挡的，来自命令式语言，所以这是可以理解的，但它使你的算法难以分析。

从问题中可以清楚地看出，您的算法必须是指数的，因为它以指数方式枚举了许多排列。

您的复杂性的主要因素是您对输入中的每个元素进行的递归调用，使列表更小一个元素。因此，您的递归深度是输入中元素的数量，每一步中的递归调用次数也是该数量。因此，我们得到的复杂性是 O(n^n) = O(2^(n*ld(n)))

现在，如果您以最佳方式返回结果，这将是您的复杂性，但您使用的是 result ++= plist :: Nil。首先，这不是函数式风格，没有充分理由应该避免。但是如果你这样做，你应该使用一个可变结构（例如 ListBuffer）或者至少添加到一个列表中。在这里，您附加到一个长度为线性的列表。所以整个事情是你追加到列表的元素数量的二次方，这是指数级的。所以你得到的复杂性实际上是

O((2^(n*ld(n)))^2) = O(2^(2*n*ld(n)))

即使在 O 表示法中，指数中的常数也确实有所不同。

将 result ++= plist :: Nil 替换为 result = plist :: result 可为您的算法提供最佳的渐近复杂度并使其速度大大加快。

然而，您的算法还有一些其他问题不会影响渐近复杂度：

i <- rlist.indices不需要遍历索引，直接遍历x <- rlist元素即可。这也快得多，因为对 List 的基于索引的访问需要线性时间。
您的方法 drop 过滤列表以删除一个元素。如果你使用一个集合而不是一个列表，你可以直接有效地删除元素，这可以更简单和更快地实现。
您可以通过附加一个列表来附加到您的 plist：plist ++ (x :: Nil)，但您可以直接附加到列表，这样更不复杂且速度更快：x :: plist。此外，还有一个 :+ 运算符，它只附加一个元素。您不必将元素放入列表中只是为了追加它。

这是您的代码的清理版本：

def permute(list:List[Int]):List[List[Int]] =
  if(list.isEmpty) {
    Nil
  } else {
    var result: List[List[Int]] = Nil

    def recursion(plist: List[Int], rlist: List[Int]): Unit = {
      if (rlist.isEmpty)
        result = plist :: result

      if (plist != list.reverse)
        for (x <- rlist) {
          val xDropped = drop(x, rlist)
          val newPList = x :: plist
          recursion(newPList, xDropped)
        }
    }

    recursion(Nil, list)
    result
  }

现在已经相当快了。

如果不考虑性能，我会这样做：

def perm[T](elements: Set[T]): List[List[T]] =
  if(elements.isEmpty)
    List(Nil)
  else
    for {
      element <- elements.toList
      rest <- perm(elements - element)
    } yield
      element :: rest

这更清晰、更简单，而且几乎与代码的优化版本一样快。实际上，我很惊讶你的清理版本更快，但有两个原因：首先，无论如何我们都必须遍历集合中的所有元素，所以能够删除单个元素并不是什么优势，并且那么对列表的迭代比对集合的迭代更快。其次，我的算法遍历结果集并转换其元素，这似乎比构建完整结果要慢一些。

这个版本终于和你清理过的版本一样快或快一点点：

def perm[T](elements: List[T], result: List[T]): List[List[T]] =
  if(elements.isEmpty)
    List(result)
  else
    for {
      element <- elements
      res <- perm(elements.filter(_!=element), element :: result)
    } yield res
def perm[T](elements: List[T]): List[List[T]] = perm(elements, Nil)

可能有一种更快的命令式方法，但这应该是 "good enough"。 Scala标准库里的版本好像比这个慢很多

当然还有一个更快更短的函数版本，它使用列表插入操作：

def insert[T](elem: T, list: List[T]) =
  (0 to list.size).map{
     pos => list.take(pos) ++ (elem :: list.drop(pos))
  }

所以现在我们可以简单地这样做：

def perm[T](elements: List[T]) =
  elements.foldLeft(List(List[T]())){
    (results, element) => results.flatMap{insert(element,_)}
  }

所以按照直接方法 "permute n elements by permuting n-1 and inserting the next element at every position" 结果是最短最快的...

我的排列函数编码 scala 上的大 O-Notation

Big O-Notation on my permutation function coded scala

algorithm

big-o

scala