Finde heraus, die Laufzeit eines rekursiven Algorithmus (Master-Therorem)

Question

Hier ist der Algorithmus, dessen Laufzeit I berechnen möchten:

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

n Teil der positiven natürlichen Zahlen, c0 und c1 Konstanten sind . Hier

ist der Algorithmus in Java-Code:

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; 
    } 

Ich bin für einen Ansatz oder eine Erläuterung Beispiel suchen.

Answer 1

Hmm, habe das nicht lange gemacht, aber da niemand Antwort gab, lass es mich versuchen. Du erstellst hier im Grunde einen Baum mit zwei wichtigen Kindern. Die linke basiert auf temp = n/4d und die rechte basiert auf temp2 = n * (5/12d) + (3/2d). Die Frage ist also, wie tief ist dieser Baum? Seit n/4d wird unter 20 schneller als n * (5/12d) + (3/2d) enden wir kümmern uns nur um richtiges Kind. Also Frage ist, wie weit rechts Kinder sind basierend auf n? Wie wir iterieren, haben wir diese:

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) 
... 

Hier können wir auch 3/2d Teil sowie alles rund um sie ignorieren, so dass wir dies:

n * (5/12)^k < 20 

Wo k ist die Zahl Schritte am weitesten rechts Kind zu erreichen, so haben wir:

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) 

Da dies:

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

ist eine bestimmte Anzahl, wir es ...

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

Da ignorieren können:

log_2 (5/12) < 0 

wir sind links:

k = log_2(n) = lgn 

Wie erwartet, da wir Arbeit nur mit Baum, erhalten Sie O(n) = lg(n).