O(logn) и алгоритм отношений

Question

Я до сих пор не могу понять анализ алгоритма O(logn)

Таким образом, если есть вложенный цикл for, где его внутренний цикл увеличивается / уменьшается либо умножением, либо делением, то это Big-theta (logn), где его основание - на сколько оно делится или умножается?

Например:

for(int i=0;i<n;i++) {
for(int j=1; j<n; j*=5) ...

this is Big-theta(logn) with base 5 since it is multiplied by 5?

Другой пример:

for(int i=n;i>0;i--) {
for(int j=i; j>0; j/=10) ...

this is 
Big-theta(logn) with base 10 since it is divided by 10?

Я правильно понял?

Другой вопрос:

Big-theta (logn) работает только для вложенного цикла? (для цикла внутри цикла for)

Answer 1

Если мы можем посчитать, сколько раз конкретный for цикл выполняется, то мы можем легко понять сложность. Мы можем начать с примера простого цикла for.

Рассмотрим следующее для цикла:

for(int i=1;i<=m;i++)
{
    //....
}

Теперь здесь, если мы хотим найти то, сколько раз это for цикл запускается, то мы можем сделать это, написав ряд (как это единообразный ряд) и найти, какой термин > m(limit), Таким образом, мы можем легко найти количество итераций, необходимых для этого for петля.

В этом примере, если мы запишем все возможные значения i,

1,2,3,4,5,......,m

Эта серия - Арифметическая прогрессия. Теперь у нас есть уравнение для нахождения n-th срок серии как {a(n) = a(1)+(n-1)*d}, Вот d=1, a(1)=1 теперь нам нужно найти максимальное значение n такое, что a(n)<=m,

Мы можем сделать это, просто поместив a(n)=m и найти значение n, Так вот

m = 1+ (n-1)*1
m = 1+n-1
m = n
n = m.

Так что здесь общее количество итераций будет m и, следовательно, мы можем сказать, что сложность этого цикла O(m),

Теперь рассмотрим пример, который вы дали,

for(int j=1; j<n; j*=5)...

Вот если вы напишите все значения j тогда серия будет 1,5,25,125,..... и теперь эта серия является геометрической прогрессией. Формула для поиска n-th срок a(n) = a(1)*(r^(n-1)) и здесь a(1)=1 and r=5,

Сейчас ставлю n(limit)на месте a(n) чтобы увидеть, сколько раз выполняется цикл, и давайте переименовать лимит n как m чтобы устранить путаницу,

a(n) = a(1)*(r^(n-1))
m = 1*(5^(n-1))
m = 5^(n-1)
Now take log of base 5 on both side
log (m) = (n-1) //log is of base 5
n = log(m)+1 

Таким образом, мы можем найти здесь, что все необходимые итерации n = log(m)+1 где log - база 5. После удаления константы можно сказать, что этот цикл имеет сложность O(log m) с базой 5.

То же самое для второго примера вашего вопроса, если вы напишите серию j, Ты получишь n,n/10,n/100,.... так же и Geometric Progression с a(1)=n , r= 1/10 и здесь a(n) было бы 1 как нам нужно найти этот термин. Если вы найдете общее количество итераций, вы получите его как log n с основанием 10.

Big-theta (logn) работает только для вложенного цикла? (для цикла внутри цикла for)

Это не обязательно. Предположим, у нас есть только один цикл, который имеет следующий формат,

for(int i=1;i<=n;i*=2)

Этот цикл также имеет O(log n) сложность и это не внутренний цикл. Так что это зависит от операции приращения вашего цикла for. Он определяет общую сложность цикла for.