Существует полезный принцип для рассуждений о нотации big-O, который выглядит следующим образом:
Если вы сомневаетесь, работайте наизнанку!
Более конкретно, если вы Вы пытаетесь выяснить сложность всех oop гнезд, начните с самого внутреннего l oop и продолжайте заменять его более простым выражением, суммирующим объем проделанной работы.
В вашем случае у вас есть эти l oop:
for (a = 1 ; a<n ; a= 2*a) do {
for (b=n; b > 0; b=b-a) do {
}
}
Давайте начнем с внутреннего l oop:
for (b=n; b > 0; b=b-a) do {
}
Сколько раз этот l oop будет работать? Итак, мы начинаем с b, равного n, и на каждой итерации b уменьшается на a. Это означает, что число итераций этого l oop примерно равно n / a, поэтому сложность этого l oop равна Θ (н / д). Поэтому мы можем заменить внутреннюю l oop на что-то с эффектом "do Θ (n / a) work", чтобы получить эту более простую структуру:
for (a = 1 ; a<n ; a= 2*a) do {
do Θ(n / a) work;
}
Теперь давайте подумаем о том, сколько это работает Я oop делает. Поскольку объем работы внутри l oop зависит от значения a, мы не собираемся умножать количество итераций на работу, выполненную за итерацию, поскольку работа, выполненная за итерацию, не является постоянной , Вместо этого мы добавим, сколько работы сделано на каждой итерации l oop.
Обратите внимание, что значение a увеличивается как 1, 2, 4, 8, 16, 32, .. ., пока мы не перешагнем через n. Включение этих значений в работу, выполняемую внутри l oop, дает время выполнения
Θ (n / 1 + n / 2 + n / 4 + n / 8 + n / 16 + .. .)
= n Θ (1/1 + 1/2 + 1/4 + 1/8 + 1/16 + ...)
Вы можете распознать, что сумма 1/1 + 1/2 + 1/4 + 1/8 + ... случается, сходится к 2. (Вы понимаете, почему?) В результате мы имеем, что время выполнения этого кода
n Θ (2)
= Θ (n).
Таким образом, общая работа, выполненная здесь, составляет Θ (n) .
Основными методами, которые мы использовали для определения этого, были следующие:
- Работа изнутри, замена каждого l oop сводкой того, сколько работы он выполняет.
- Если счетчик al oop увеличивается на k на каждой итерации и останавливается на n, l oop выполняется в общей сложности Θ (n / k) итераций. (Это в равной степени применимо, если мы запустим его в обратном направлении и начнем с n, уменьшаясь на k.)
- Сумма геометрии c серии 1 + 1/2 + 1/4 + 1/8 + 1 / 16 + ... до бесконечности равно 2.
- Если работа, выполняемая al oop, является постоянной для каждой итерации, просто умножьте работу для каждой итерации на количество итераций. Если работа, выполненная за одну итерацию, не такова, часто проще подвести итог работы по всем l oop итерациям, а затем попытаться упростить сумму.
Надеюсь, это поможет!