Выясните время работы рекурсивного алгоритма (мастер-Therorem)

Question

Вот алгоритм которого время работы я хочу, чтобы вычислить:

T(n) = { 
     c0 * n, if n <= 20 
     T(roundUp(n/4)) + T(roundUp(5/12 * n + 3/2)) + c1*n, if n > 20 
     } 

п является частью положительных натуральных чисел, c0 и c1 константа ,

Вот алгоритм в Java-коде:

public static void main(String[] args) { 
     for (int i = 20; i < 100; i++) { 
      System.out.println("i: " + i + " : " + rec(i, 1, 1)); 
     } 
    } 

    public static int rec(int n, int c0, int c1) { 
     int res = 0; 
     if (n <= 20) { 
      res += c0 * n; 
     } else { 
      double temp = n/4d; 
      double temp2 = n * (5/12d) + (3/2d); 
      res += rec((int) Math.ceil(temp), c0, c1) + rec((int) Math.ceil(temp2), c0, c1) + c1 * n; 
     } 
     return res; 
    } 

Я ищу подход или объяснение пример.

Answer 1

Хм, не делал этого в течение длительного времени, но так как никто не дал ответа, позвольте мне попробовать. Вы в основном создаете дерево здесь, с двумя важными детьми. Левая часть основана на temp = n/4d, а правая - на temp2 = n * (5/12d) + (3/2d). Итак, вопрос в том, насколько глубоко это дерево? Так как n/4d будет в конечном итоге под 20 быстрее, то n * (5/12d) + (3/2d) мы заботимся только о правильном ребенке. Итак, вопрос в том, насколько далеко правы дети, основанные на n? Как мы итерацию, мы имеем следующее:

n * (5/12d) + (3/2d) 
ceil(n * (5/12d) + (3/2d)) * (5/12d) + (3/2d) 
ceil(ceil(n * (5/12d) + (3/2d)) * (5/12d) + (3/2d)) * (5/12d) + (3/2d) 
... 

Здесь мы также можем игнорировать 3/2d часть, а также все связанные с ним, так что мы получаем это:

n * (5/12)^k < 20 

Где k это число шагов, чтобы достичь наиболее далеко правильного ребенка, так что мы имеем:

n * (5/12)^k < 20 
k = log_(5/12) (20/n) 
k = log_2(20/n)/log_2 (5/12) 
k = (log_2 (20) - log_2(n))/log_2 (5/12) 

Поскольку это:

k = log_2 (20)/log_2 (5/12) 

это конкретное число, мы можем игнорировать его ...

k = - log_2(n)/log_2 (5/12) 

С:

log_2 (5/12) < 0 

мы остались с:

k = log_2(n) = lgn 

Как и следовало ожидать, так как мы работайте только с деревом, вы получаете O(n) = lg(n).