Laufzeit des folgenden Algorithmus?

Question

Ein Divide and Conquer-Algorithmus löst ein Problem der Größe n, indem er ihn in 2 Unterprobleme unterteilt, jede mit der Größe n-1, und benötigt O (n) Zeit, um ihre Lösungen zu kombinieren. Was ist die Laufzeit dieses Algorithmus?

Ich bin nicht ganz sicher, wie diese Wiederholungsbeziehung zu strukturieren und zu bestimmen, was die Laufzeit ist. Ist die folgende Beziehung korrekt?

T (n) = 2T (n-1) + O (n)

Wie kann ich die Laufzeit von diesem erhalten, wenn ja?

Vielen Dank!

Answer 1

Ja, Ihre Rekursionsbeziehung beschreibt Ihr Problem korrekt. Um die Dinge zu konkretisieren, sagen wir mal, die Rekursion ist. T(n) = 2T(n-1) + n (das +n ist eher als +O(n)

Dann teleskopier die Rekursion (und unter der Annahme, T (0) = 0)

T(n) = n + 2(n-1) + 4(n-2) + 8(n-3) + ... + 2^n(n-n) 
    = (1 + 2 + 4 + ... + 2^n)n - (0*2^0 + 1*2^1 + ... + n*2^n) 
    = n*(2^(n+1)-1) - 2(n*2^n-2^n+1) 
    = 2^(n+1) - n - 2 

prüfen. das ist richtig:

2T(n-1) + n 
    = 2(2^n - (n-1) - 2) + n 
    = (2^(n+1) - 2n + 2 - 4) + n 
    = 2^(n+1) - n - 2 
    = T(n)