Как рассчитывается сложность времени для цикла - Swift

Question

Я дал два образца для циклов с разной временной сложностью. Один квадратичный, а другой логарифмический. Может кто-нибудь помочь мне, почему временные сложности меняются, так как оба кода повторяются одинаковое количество раз, но с разными операциями?

Что является фактором сложности времени? Нет раз или операции?

//Quadratic O(n^2)
var c = 0
for i in 1...100{
    c = Int(pow(Double(i), 2))
}

//Logarithamic O(log n)
var d = 0
for i in 1...100{
    d = Int(log(Double(i)))
}

Answer 1

Да, сложность по времени, по сути, состоит в том, сколько раз выполняется некоторая задача постоянной длины при увеличении числа итераций.Излишне говорить, что не следует путать сложность цикла O (n ^ 2) или O (log n) с вычислениями pow(..., 2) или log() внутри цикла.Это две совершенно разные проблемы.

Так что это будет подпрограмма O (n), в которой необходимое время линейно увеличивается с числом итераций, n:

for i in 0 ..< n {
    // some task whose duration doesn’t not change with respect to `n`
}

Это будет классическая процедура O (n ^ 2), где необходимое время увеличивается с квадратом числа итераций, n:

for i in 0 ..< n {
    for j in 0 ..< n {
        // some task whose duration doesn’t not change with respect to `n`
    }
}

Классический пример O (logn) подпрограммой будет биномиальный поиск в некотором уже отсортированном массиве, где необходимое время увеличивается с увеличением количества итераций, n.Т.е. с помощью еще одной итерации вы можете найти значение в массиве, в два раза превышающем его размер.

Answer 2

Два цикла имеют одинаковую сложность времени - O (1) постоянное время, потому что они всегда будут выполняться 100 раз. Ничего о них

Как вы, возможно, знаете, временная сложность измеряет, как время, необходимое для выполнения алгоритма, изменяется как переменная , изменяется . Например, этот цикл имеет временную сложность O (n):

for i in 0..<n {
    print(i)
}

По мере увеличения n время, необходимое для запуска этого цикла, увеличивается линейно , следовательно, O (n).

Этот цикл будет O (n ^ 2):

for i in 0..<(n*n) {
    print(i)
}

Этот цикл будет O (log (n)):

for i in 0..<Int(log(n)) {
    print(i)
}

(Очевидно, есть другие способы сделать петли O (n ^ 2) и O (log (n)))

Я думаю, что циклы, которые вам даны, просто должны иллюстрировать различные временные сложности путем построения «графика» необходимого времени, которое увеличивается с ростом n. Как видно из скриншота, цикл O (log (n)) строит график log (n).