0 Daumen
969 Aufrufe

Geben Sie mit Hilfe des Master-Theorems gute asymptotische Schranken für die folgenden Rekursionsgleichungen an.

a) \( T(1)=1, T(n)=4 \cdot T\left(\frac{n}{2}\right)+n \)

b) \( T(1)=1, T(n)=4 \cdot T\left(\frac{n}{2}\right)+n^{2} \)

c) \( T(1)=1, T(n)=4 \cdot T\left(\frac{n}{2}\right)+n^{3} \)

von

1 Antwort

+1 Daumen

Als erstes muss man die Laufzeitklasse der Aufwandsfunktion bestimmt werden:

Das Mastertheorem lässt sich für eine Rekurrenz T 

T(n) = a*T(n/b) + f(n)

anwenden, wenn eine der folgenden Bedingungen erfüllt ist:

i) f ∈ Ο(nlogb(a)-e) für ein e > 0

ii) f ∈ Θ(nlogb(a))

iii) f ∈ Ω(nlogb(a)+e) für ein e > 0 und für ein c∈]0, 1[: af(n/b) ≤ c*f(n)

 

In jedem der Beispiele ist a=4, b=2, also muss das Verhältnis zwischen f und n2 bestimmt werden.

a) Für ε=1 gilt:

f∈ O(n2-1) = O(n)

Damit gilt:
T ∈ Θ(n2)

b) Es gilt f ∈ Θ(n2)

Also:

T ∈ Θ(n2 log(n))

c) Es gilt f∈ Ω(n3) mit ε=1. Nun muss noch die zusätzliche Bedingung erfüllt sein:
4*(n/2)3 ≤ c*n3

1/2 n3 ≤ c*n3

Offenbar tut zum Beispiel c = 1/2 den Job.

Damit folgt: T ∈ Θ(f(n)) = Θ(n3)

von 10 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community