2

以下函数的复杂性（Big-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)）。

4

1 回答 1

3

我相信您的代码结构可以像这样更简单地查看：

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 * (nm)) 其中 m 是与您的输入大小相关的非常数​​，这是您在循环中不执行 O(n) 操作的次数。这简化为 O(n^2 - n*m)，即 O(n^2)。您的循环的复杂性大于您的类型，因此您的最终复杂性为 O(n^2)。

于 2017-06-05T19:59:10.413 回答