1
何だろう、以下の機能のための複雑さ（ビッグ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）ではありません）。