rekursive Zeitgleichung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:59 Di 23.10.2007 | | Autor: | Dani7 |
| Aufgabe | Zeigen Sie eine obere Schranke für folgende rekursive Zeitgleichung durch iteratives einsetzen:
T(n)= T(n-a)+n,
T(n)=O(1) für n <= 1,
wobei a eine Konstante ist. |
Durch iteratives einsetzen habe ich folgende Gleichungen erhalten:
T(n)= T(n-2a)+2n,
T(n)= T(n-4a)+4n,
T(n)= T(n-8a)+8n,
T(n)= T(n-16a)+16n,...
allgemein kann man nun sagen:
a) T(n) = T(n-K*a) +K*n,
oder
b) T(n) = T(n-2^(n-1)*a -n*2^(n-1),
Da ich nicht wußte wie man mit b) umgehen kann, habe ich versucht mit a) weiterzurechnen.Dabei habe ich versucht herauszufinden, wann der Term
T(n-K*a) zu T(1) wird, nämlich dann, wenn K= (n-1)*a
dann sieht die Gleichung so aus:
T(n)= T(n- a*(n-a)/a) +n*(n-1)/a => weil T(n) = O(1) für n<= 1:
T(n)= O(1) + (n-1)*n/a
also
T(n) = O(1) +(n²-n)/a =>
T(n) = O(1) +O(n²) =>
T(n) =O(n²)
--------------
Ich bin mir nicht sicher ob dieser Beweis so aussehen kann und darf und wollte fragen ob mir jemand sagen kann ob das so richtig ist oder ob man das so nicht machen kann.
Wäre dankbar wenn sich das jemand ansehen könnte.
lg Daniela
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:57 Di 23.10.2007 | | Autor: | leduart |
Hallo
> Zeigen Sie eine obere Schranke für folgende rekursive
> Zeitgleichung durch iteratives einsetzen:
> T(n)= T(n-a)+n,
> T(n)=O(1) für n <= 1,
> wobei a eine Konstante ist.
> Durch iteratives einsetzen habe ich folgende Gleichungen
> erhalten:
>
> T(n)= T(n-2a)+2n,
daraus habe ich T(n-2a)=T(n-4a)+2*(n-2a)
T(n)=T(n-4a)+2n-4a
also denk ich, dass dein Anfang nicht stimmt.
Dann muss ich den Rest nicht überprüfen.
(das setzt irgendwie vorraus, dass n-2a wieder ne ganze Zahl ist, falls n ne ganze Zahl ist, oder ist das nicht so gemeint?
wenn ich [mm] a=\pi [/mm] setze erfüllt die Gleichung T(x)=sinx+x deine Bedingung mit T(0)=0 sonst cosx+x T(0)=1 (glaub ich, prüfs nach!)
Gruss leduart
> T(n)= T(n-4a)+4n,
> T(n)= T(n-8a)+8n,
> T(n)= T(n-16a)+16n,...
>
> allgemein kann man nun sagen:
>
> a) T(n) = T(n-K*a) +K*n,
>
> oder
>
> b) T(n) = T(n-2^(n-1)*a -n*2^(n-1),
>
> Da ich nicht wußte wie man mit b) umgehen kann, habe ich
> versucht mit a) weiterzurechnen.Dabei habe ich versucht
> herauszufinden, wann der Term
> T(n-K*a) zu T(1) wird, nämlich dann, wenn K= (n-1)*a
>
> dann sieht die Gleichung so aus:
> T(n)= T(n- a*(n-a)/a) +n*(n-1)/a => weil T(n) = O(1) für
> n<= 1:
>
> T(n)= O(1) + (n-1)*n/a
>
> also
> T(n) = O(1) +(n²-n)/a =>
>
> T(n) = O(1) +O(n²) =>
>
> T(n) =O(n²)
> --------------
>
> Ich bin mir nicht sicher ob dieser Beweis so aussehen kann
> und darf und wollte fragen ob mir jemand sagen kann ob das
> so richtig ist oder ob man das so nicht machen kann.
> Wäre dankbar wenn sich das jemand ansehen könnte.
>
> lg Daniela
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:51 Di 23.10.2007 | | Autor: | deat |
Die allgemeine Formel dazu sollte:
T(n-Ka)+Kn-1/2*K(K-1)*a
lauten.
|
|
|
| |
|
Wäre es möglich zu deiner Antwort
auch eine Erklärung zu bekommen?
Mfg Philipp
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:03 Mi 24.10.2007 | | Autor: | leduart |
Hallo
wo ist dein Versuch das selbst herzuleiten? und dann mit der im post genannten Formel zu überprüfen?
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Fr 26.10.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
