rekursive Zeitgleichung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:00 Di 11.11.2014 | | Autor: | gismot |
| Aufgabe 1 | Durch iteriertes Einsetzen eine obere Schranke finden
es gilt T(n)=O(1) für n<=1
T(n)=T(n-a)+n
wobei a Element N a >=1 eine Konstante ist |
| Aufgabe 2 | Durch iteriertes Einsetzen eine obere Schranke finden
es gilt T(n)=O(1) für n<=1
[mm] T(n/2)+n^2 [/mm] |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo zusammen!
Ich hab mir BSP 1. z angeschaut, und habe als erstes einmal die Gelichung in sich selbst eingesetzt und komme auf:
T(n)=T(n-a)+n
1. =T(((n-a)+n)-a)+n
2. =T(((((n-a)+n)-a)+n)-a)+n
=T(3n-3a)+n
3. =T(((3n-3a)+n)-a)+n
=T(4n-4a)+n
Allgemein ergibt das für mich folgende Bildungsregel:
T(kn-ka)+n
laut dem post aber https://matheraum.de/read?t=312129, stimmts nicht.
Ich würde dann wie folgt weitergehen:
ein c suchen das T(n) erfüllt (Abbruchbedingung)und dies in die Formel einsetzen.
=T(bla) kann ich mit O(1) gleichsetzen+ was mir dann übrigbleit-Konstanten wäre meine Obere Schranke
Das es ein c gibt wäre dann mein Beweis.
Meine Fragen:
Stimmt meine allgemeine Form oder die vom Fragesteller oder die die zwischendurch gepostet wurde?
Reicht es wenn ich ein c finde das die Gleichung erfüllt as beweis, das mein Endergebniss die Obere Schranke ist
Zu B hätte ich den Ansatz
T(n) [mm] \le [/mm] c*n*logn für c >0
[mm] T(n)=6T(n/2)+n^2 [/mm] n [mm] \le [/mm] 1
[mm] T(n)=6T(n/2)+n^2
[/mm]
[mm] \le 6(cn/2log(n/2)+n^2 [/mm] | log [mm] \equiv [/mm] log basis 6
[mm] =cnlog(n/2)+n^2 [/mm] | log(n/2)=log(n)-log(2)
[mm] \le [/mm] cnlogn-cn+n | c>1
[mm] \equiv [/mm] cnlogn
Wie würde ich hier auf meine Obere Schranke kommen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Fr 14.11.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
