Rekurrenz abschätzen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | [mm] T(n)=\begin{cases} c_0 n, & \mbox{für } n\le n_0, n_0 \ge 35 \mbox{ geeignet gewählt} \\ T(n/5) + T(\bruch{7}{10}n + 2.5) + c_1 n , & \mbox{falls } n \ge n_0 \mbox{ } \end{cases}
[/mm]
finden Sie eine Funktion f, so dass T(n) [mm] \in [/mm] O ( f(n)) gilt und beweisen Sie ihre Behauptung. |
Hallo,
ich habe zunächst probiert T nach oben und unten abzuschätzen, indem ich T(n/5) + T(n/5) + [mm] c_1 [/mm] n und [mm] T(\bruch{7}{10}n) [/mm] + [mm] T(\bruch{7}{10}n [/mm] ) + [mm] c_1 [/mm] n probiert habe abzuschätzen,indem ich die Summen
[mm] \summe_{i=0}^{log_{5}n - 1} c_1 [/mm] n + [mm] 2^{log_{5}n} c_0 [/mm] n und [mm] \summe_{i=0}^{log_{\bruch{10}{7}}n - 1} c_1 [/mm] n + [mm] 2^{log_{\bruch{10}{7}}n} c_0 [/mm] n
dabei bekam ich raus das [mm] n^{2.4...} \le [/mm] f(n) [mm] \le n^{7,45} [/mm] sein muss.
Kann das soweit stimmen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Di 04.05.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
