www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Algorithmen und Datenstrukturen" - Rekursive Zeitgleichungen
Rekursive Zeitgleichungen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rekursive Zeitgleichungen: Aufgabe 1
Status: (Frage) überfällig Status 
Datum: 16:54 Do 27.09.2012
Autor: tommy987

Aufgabe 1
Geg. ist folgende Gleichung:

T(n) = 5T(n-3)

Gesucht ist eine asymptotische Schranke.

Aufgabe 2
T(n) = [mm] 4T(\frac{n}{5}) [/mm] + O(1)

Gesucht ist ebenfalls eine asymptotische Schranke.

Bis jetzt bin ich auf dem Ergebnis T(n) = [mm] 5^k [/mm] * T(n-3*k)
und k = [mm] \bruch{1}{n-3} [/mm] mittels der Methode des iterativen Einsetzens gekommen.
Wie komm ich jetzt auf die obere Schranke ( O(...) )?

Beim 2. Beispiel würde micht interessieren, ob ich hier die Mastermethode anwenden kann? und falls JA, wie?

Oder kann man hier vielleicht sogar die Substitutionsmethode verwenden?

lg
Thomas4

        
Bezug
Rekursive Zeitgleichungen: Antwort
Status: (Antwort) fertig Status 
Datum: 23:16 Do 27.09.2012
Autor: reverend

Hallo Thomas,

vielleicht verstehe ich ja nur die Notation nicht, aber so sind die Aufgabenstellungen wenig sinnvoll.

(1)

> Geg. ist folgende Gleichung:
>  
> T(n) = 5T(n-3)
>  
> Gesucht ist eine asymptotische Schranke.

(2)

> T(n) = [mm]4T(\frac{n}{5})[/mm] + O(1)
>
> Gesucht ist ebenfalls eine asymptotische Schranke.

Zu (1)

>  Bis jetzt bin ich auf dem Ergebnis T(n) = [mm]5^k[/mm] * T(n-3*k)
>  und k = [mm]\bruch{1}{n-3}[/mm] mittels der Methode des iterativen
> Einsetzens gekommen.
>  Wie komm ich jetzt auf die obere Schranke ( O(...) )?

Nehmen wir mal ein Beispiel. Sei T(1)=0, T(2)=-0,3714 und T(3)=200.001.229

Dann definiert die rekursive Formel faktisch drei verschiedene Folgen, die vollkommen unabhängig voneinander sind. Sei [mm] m\in\IN_0. [/mm]
Die eine umfasst T(1), T(4), T(7), ..., T(3m+1) und ist konstant Null.
Die zweite umfasst alle T(3m+2) und strebt gegen [mm] -\infty. [/mm]
Die dritte umfasst alle T(3m) und strebt gegen [mm] +\infty. [/mm]
Und nun?

Zu (2)

> Beim 2. Beispiel würde micht interessieren, ob ich hier
> die Mastermethode anwenden kann? und falls JA, wie?
>  
> Oder kann man hier vielleicht sogar die
> Substitutionsmethode verwenden?

Sagt mir nichts, was wahrscheinlich an mir liegt.
Was ist O(1)? Und wieso darf man n einfach fünfteln?

Grüße
reverend


Bezug
        
Bezug
Rekursive Zeitgleichungen: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:20 Mo 01.10.2012
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]