Bestimmen Sie für die Rekursionsgleichung
T(n)= 9*T(n/3) + n2 + √n + 3*n + 3
Wir haben die Rekursionsgleichung$$T(n)= a T\left( \frac{n}{b} \right)+f(n)$$wobei:$$a=9 \geq 1 \\ b=3>1 \\ f(n)=n^2+ \sqrt{n}+3n+3$$$$n^{\log_b a}=n^{\log_3 9}=n^{\log_3 3^2}=n^2$$Außerdem haben wir dass: $$f(n)=n^2+ \sqrt{n}+3n+3= \Theta(n^2)$$Also:$$f(n)=\Theta(n^{\log_b a})$$Was haben wir also vom 2ten Fall vom Master theorem?
T(n) ∈ Θ(n2 *log(n) ) ?
Genau! Denn vom 2ten Fall vom Master Theorem haben wir dass $$T(n) \in \Theta(n^{\log_b a} \log n)$$
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos