大O-符号编码斯卡拉

-3

下面的代码是实施名单置换元素，由斯卡拉大O-符号编码斯卡拉

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符号

由于该方法的详细介绍，有一个愉快的一天。

来源

2016-02-06 이도현

https://en.wikipedia.org/wiki/Big_O_notation – Chris

那么，你的算法太复杂了，因为很多次优步骤。如果您首先看到Scala API，并且它来自命令式语言，那么Scala API非常令人难以置信，所以这是可以理解的，但它会让您的算法很难分析。

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

您的复杂性的主导因素是递归调用，您为输入中的每个元素执行的递归调用列表中的一个元素较小。因此，递归深度是输入中元素的数量，每个步骤中的递归调用数与该数一样。因此，我们得到的复杂性是，如果你以最优方式返回结果，那么这将是你的复杂性，但你是复杂的使用result ++= plist :: Nil。首先，这不是功能性的风格，没有很好的理由，应该避免。但是，如果你这样做，你应该使用一个可变结构（例如ListBuffer）或者至少在列表前加上一个。在这里，你追加到一个长度为线性的列表。因此，整个事件在追加到指数列表的元素的数量上是二次的。所以，你得到的复杂性是什么，其实

O（（2 ^（N * LD（N）））^ 2）= 0（2 ^（2 * N * LD（N）））

即使在O-notation中，指数中的常量也会有所作为。

替换result ++= plist :: Nilresult = plist :: result为您的算法提供了最优的渐近复杂度，并使其显着更快。

但是也有一些其他的问题，与你的算法，不影响渐近复杂性：

没有必要遍历指数与i <- rlist.indices，你可以直接在元素x <- rlist迭代。由于基于索引的List访问需要线性时间，因此这也更快。
您的方法将过滤列表以删除一个元素。如果使用一个集合而不是一个可以直接高效地删除元素的列表，这可以更简单快捷地实现。
您追加到你的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)

有可能是更快的，必要的方式来做到这一点，但是这应该是“足够好” 。斯卡拉标准库中的版本似乎比这慢很多。

再有就是当然的使用上表的插入操作的速度更快和更短的功能版本：

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,_)} 
    }

因此，按照直接方法“通过排列n-1排列n个元素并在每个位置插入下一个元素”原来是最短和最快的...

来源

2016-02-06 16:35:54 dth

大O-符号编码斯卡拉

回答

相关问题