-         

Ergebnis 1 bis 5 von 5

Thema: Rekurrenz interpretieren

  1. #1
    Neuer Benutzer
    Registriert seit
    13.10.2005
    Alter
    37
    Beiträge
    2

    Rekurrenz interpretieren

    Anzeige

    Hey Leute,

    ich habe hier die Rekurrenz eines Algorithmus und soll diese nun interpretieren, und zwar um welche Art von Algorithmus es sich dabei handelt.

    T(n) = T(n/3) + 5 für n >= 2

    Vielleicht weis jemand eine Antwort darauf und kann mir helfen.

    Schon im voraus Danke

  2. #2
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    20.11.2003
    Ort
    Chemnitz
    Alter
    36
    Beiträge
    129
    Vielleicht kannst du die komplette Aufgabenstellung im Originallaut posten?
    Grüße,
    zefram

    --
    www.roboking.de - Jetzt bis zum 31. Mai 2007 anmelden für die fünfte Runde des großen Roboterwettbewerbs für Schüler aus Deutschland, Österreich und der Schweiz -

  3. #3
    Gast

    Aufgabenstellung

    Okay, hier kommt die ganze Aufgabenstellung, a.) und c.) hab ich schon gelöst.

    Rekurrenzen

    1. Entfaltung + Beweisen
    a) Lösen Sie folgende Rekurrenz mittels Entfaltung:
    T(1) = 5
    T(n) = T(n/3) + 5 für n ≥ 2
    b) Um welche Art von Algorithmus handelt es sich hier? Interpretieren Sie
    die Rekurrenz.
    c) Beweisen Sie (mittels Raten und Beweisen), dass Ihr Ergebnis aus 1.a)
    richtig ist.

    Antwort a.) und b.): O(T(n)) = log(n)

  4. #4
    Neuer Benutzer
    Registriert seit
    13.10.2005
    Alter
    37
    Beiträge
    2
    Sorry, war leider nicht angemeldet.

  5. #5
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    13.05.2005
    Ort
    Wien
    Alter
    44
    Beiträge
    137
    Google mal unter "Erzeugende Funktionen", damit hat mich der Prof. Baron auf der TU Wien damals gequält. Der Kerl hat auch nette Bücher geschrieben.. nachlesen kann nicht schaden ... was ich mich nur frage: was ist T(n/3)? ist T(2/3) denn definiert? ist das T(1) oder T(0)?

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •