Найти рекуррентное уравнение из алгоритма

Question

Я должен найти уравнение повторения из этого алгоритма:

    ALGO(n)
    if n <= 2 then return(0)
    else
        y = ALGO(n/3)
        i = 2^n
        while i >= 2 do
            j = (1/2) * log(i) //base 2
            while j > 0 do
                i = i/2
                j = j - 1
        z = ALGO(n/2)
        return(z+y) 

Я рассуждал об этом и пришел к выводу, что T (n) = O (1), если n <= 2 </p>

Я думаю, что внутреннее while - это O (n) (j уменьшается на 1 на каждой итерации), а внешнее while - O (logn) (i уменьшается на две на каждой итерации), давая O (n * журнал (п)):

T (n) = T (n / 3) + T (n / 2) + O (n * log (n)), если n> 2

Это хороший аргумент?

Answer 1

Два цикла while должны быть O (n):

1. i = 2^n;
2. j = (1/2) * log (i) = 1/2 * n = n/2
3. the inner while executes for n/2 times then j becomes 0, now i = i / 2^(n/2) = 2^(n/2);

Теперь эта программа вернется к шагу 1, только с уменьшением вдвое.Таким образом, два цикла должны быть:

n/2+n/4+n/8+... = O(n)

На самом деле это также можно рассматривать с более простой точки зрения.Поскольку цикл не завершится до тех пор, пока i == 1, и для каждого выполнения i = i / 2 внутренний цикл будет выполняться n раз.Представьте, что мы сглаживаем внутренний цикл и выходной цикл, i = i / 2 будет n раз, следовательно, два цикла O (n).

В заключение, T (n) = T (n/ 3) + T (n / 2) + O (n).

Надеюсь, это может быть полезно!