寻找复杂性 - Swift

Question

以下函数的复杂度（Big-O 表示法）是多少：

func sortList(_ thresholdValue: Int) -> [Int] {
    var currentValue = thresholdValue
    //Values is an array of integers - [Int]
    var valArr = values.sorted { [=11=] >  } //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 { [=11=] <= currentValue }.sorted { [=11=] >  } //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).

寻找复杂性 - Swift

Finding the complexity - Swift

algorithm

big-o

code-complexity

swift