大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-符號編碼斯卡拉

回答

相關問題