0 Daumen
585 Aufrufe

Formel als Text

Wie auch schon in der anderen Aufgabe erwähnt war ich leider krank und verstehe auch deswegen hier nur Bahnhof. Bin über jede Hilfe mir das verständlicher zu machen sehr dankbar.

Gefragt von

1 Antwort

+1 Punkt

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)

Beantwortet von 10 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...