Zeitgleichungen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Lösen Sie folgende rekursiven Zeitgleichungen auf:
1. T(n) = [mm] 7T(\bruch{3}{4}) [/mm] + Theta(n)
2. T(n) = T(n-1) + 3
3. T(n) = T(n - [mm] \wurzel{n}) [/mm] |
Hallo!
Ich habe Bsp. 1 mit der Master-Methode gelöst und habe errechnet das Fall 1 zutrifft. Somit komme ich zur Lösung:
T(n) = [mm] 7T(\bruch{3}{4}) [/mm] + Theta(n) --> [mm] Theta(n^{log_{3}7})
[/mm]
Bei Bsp. 2 komme ich auf folgendes Ergebnis:
T(n) = T(n-1) + 3 --> O(n)
Für Bsp. 3 fehlt mir noch ein wenig der Ansatz wie ich das lösen könnte. Vielleicht kann mir jemand einen Hinweis geben.
Ansonsten würde ich sehr gerne wissen ob meine ersten 2 Beispiele stimmen oder ob ich mich verrechnet habe.
Danke im Voraus
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:24 Mo 13.06.2011 | | Autor: | fred97 |
> Lösen Sie folgende rekursiven Zeitgleichungen auf:
>
> 1. T(n) = [mm]7T(\bruch{3}{4})[/mm] + Theta(n)
Was ist Theta ?
Was verstehst Du unter "auflösen " ?
> 2. T(n) = T(n-1) + 3
Das ist einfach: T(n)=T(0)+3n
> 3. T(n) = T(n - [mm]\wurzel{n})[/mm]
Jedes konstante T leistet das
> Hallo!
>
> Ich habe Bsp. 1 mit der Master-Methode gelöst und habe
> errechnet das Fall 1 zutrifft. Somit komme ich zur Lösung:
>
> T(n) = [mm]7T(\bruch{3}{4})[/mm] + Theta(n) --> [mm]Theta(n^{log_{3}7})[/mm]
Was meinst Du damit ? "--->" ?
>
> Bei Bsp. 2 komme ich auf folgendes Ergebnis:
>
> T(n) = T(n-1) + 3 --> O(n)
Das stimmt zwar, aber nochmal: Was verstehst Du unter "auflösen " ?
FRED
>
> Für Bsp. 3 fehlt mir noch ein wenig der Ansatz wie ich das
> lösen könnte. Vielleicht kann mir jemand einen Hinweis
> geben.
>
> Ansonsten würde ich sehr gerne wissen ob meine ersten 2
> Beispiele stimmen oder ob ich mich verrechnet habe.
>
> Danke im Voraus
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
> Was ist Theta ?
Ich habe das Symbol im foreneigenen Code für Theta nicht gefunden, deshalb habe ich es so hingeschrieben. Die Theta-Notation gibt eine untere Schranke für eine Funktion an.
> Das stimmt zwar, aber nochmal: Was verstehst Du unter
> "auflösen " ?
Die exakte Angabe lautet: Lösen sie die folgenden rekursiven Zeitgleichungen auf und geben Sie möglichst gute Schranken an.
Mit --> meinte ich aus dieser Zeitgleichung ergibt sich folgende Schranke. Ich weiß es ist total unschön hingeschrieben.
lg
|
|
|
|
