寻找复杂 - 斯威夫特

Question

会是什么样的复杂性（大O符号）以下功能：

func sortList(_ thresholdValue: Int) -> [Int] { 
    var currentValue = thresholdValue 
    //Values is an array of integers - [Int] 
    var valArr = values.sorted { $0 > $1 } //should be a merge sort O(nlogn) 


    for i in 0...valArr.count-1 { 
     if valArr[i] < currentValue { 
      currentValue = currentValue - valArr[i] 

     } else { 
      let tempArr = filter(valArr[0...i-1], currentValue) // O(n) - array splicing 

      if tempArr.count > 0, let updatedValue = tempArr.first { 
       currentValue = currentValue - updatedValue 

       valArr = updateArr(array: valArr, fromIndex: valArr.index(of: updatedValue)!, toIndex: i) 

       currentValue = thresholdValue 

      } else { 
       currentValue = thresholdValue - valArr[i] 

      } 
     } 
    } 

    return valArr 
} 

func updateArr<T>(array: Array<T>, fromIndex: Int, toIndex: Int) -> Array<T>{ 
    var arr = array 
    let element = arr.remove(at: fromIndex) // O(n) 
    arr.insert(element, at: toIndex) // O(n) 

    return arr 
} 

func filter(_ tempArr:ArraySlice<Int>,_ currentValue : Int) -> [Int]{ 
    for value in tempArr { // O(n) 
     if let index = values.index(of: value) { 
      tempArr.remove(at: index) // O(n) 
     } 
    } 

    return tempArr.filter { $0 <= currentValue }.sorted { $0 > $1 } //O(n) O(mlogm) 
} 

上述函数试图重新排列的整数，以致元素的序列（而不是子阵列）总计小于或等于k的值。一旦序列完成，一个新的序列（在同一个阵列中）的总和小于或等于k。我为每个可能的执行添加了可能的复杂性（不是O（1））。

Answer 1

我相信你的代码的结构可以更简单地认为是这样的：

sort values (O(nlogn) operation) 
loop over values (O(n) operation) 
    if some condition is satisfied 
    perform O(1) operation 
    else 
    perform O(n) operation 
    if some condition is satisfied 
     perform O(n) operation (updateArr) 
    else 
     perform O(1) operation 

首先你执行排序，那么你遍历你的输入，并基于该循环执行O（n）的操作一些条件。在这种情况下最糟糕的情况是，如果您在循环内执行了多次与您的输入大小相关的O（n）操作。在这种情况下，循环的时间复杂度为O（n *（n-m）），其中m是与您的输入大小相关的非常数​​，这是您在循环中不执行O（n）操作的次数。这简化为O（n^2 - n * m），即O（n^2）。你的循环的复杂度比你的循环更大，所以你最终的复杂度是O（n^2）。