Нахождение сложности - Swift

Question

Какова будет сложность (обозначение 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)).

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 * (нм)), где m - это непостоянное число, относящееся к размеру вашего ввода, то есть количество раз, когда вы не выполняете операции O (n) в вашем цикле. Это упрощает до O(n^2 - n*m), который является O(n^2). Сложность вашего цикла больше, чем у вас, поэтому ваша последняя сложность равна O(n^2).