Вычисление большой сложности O рекурсивных алгоритмов

Question

Как-то я нахожу, что получить сложность Big O для рекурсивных алгоритмов намного сложнее по сравнению с итеративными алгоритмами. Предоставьте некоторое представление о том, как я должен решить эти два вопроса.

* Предположим, что submethod имеет линейную сложность

def myMethod(n) 
    if (n>0) 
    submethod(n) 
    myMethod(n/2) 
    end 
end 

def myMethod(k,n) 
    if(n>0) 
    submethod(k) 
    myMethod(k,n/2) 
    end 
end 

Answer 1

Для вашей первой задачи, повторение будет:

T(n) = n + T(n/2) 

    T(n/2) = n/2 + T(n/4) 
    ... 
    ... 
    ... 
    T(2) = 2 + T(1) 

    T(1) = 1 + T(0) // assuming 1/2 equals 0(integer division) 

adding up we get: 

    T(n) = n + n/2 + n/4 + n/8 + ..... 1 + T(0) 

     = n(1 + 1/2 + 1/4 + 1/8 .....) + k // assuming k = T(0) 

     = n*1/(1 - 1/2) (sum of geometric series a/(1-r) when n tends to infinity) 

     = 2n + k 

Поэтому Т (п) = О (п). Помните, я предположил, что n стремится к бесконечности, потому что это то, что мы делаем в Асимптотический анализ.

Для вашей второй проблемы его легко увидеть, что мы выполняем k примитивных операций каждый раз, пока n не станет 0. Это происходит log (n) раз. Поэтому T (n) = O (k * log (n))

Answer 2

Все, что вам нужно сделать, это подсчитать, сколько раз основная операция выполняется. Это справедливо для анализа любого алгоритма. В вашем случае мы посчитаем, сколько раз вызывается submethod.

Вы можете отключить время работы от звонка myMethod(n) будет 1 + myMethod(n/2). Который вы можете далее сломать до 1 + (1 + myMethod(n/4)). В какой-то момент вы достигнете базового футляра, в log(n)-м шаге. Это дает вам алгоритм log(n).

Второй ничем не отличается, так как k постоянен все время, он снова займет log(n) время, предполагая submethod занимает постоянное время независимо от его входа.