Rekursionsgleichung bestimmen

yeha

Mitglied
Hallo,

ich finde im Internet leider keine richtige Anleitung dazu wie ich die Laufzeit zu einem rekursiven Algorithmus bestimmen kann, deshalb wende ich mich an euch, in der Hoffnung, dass ihr mir helfen könnt :D
Klar ist, dass man die Rekursionsgleichung dazu braucht, aber ich versteh nicht so richtig wie ich diesen aufstellen muss.
a*t(n/b)+f(n)
In Vorlesungsfolien habe ich gelesen, dass a die Anzahl der Unterprobleme und b die Größe der Unterprobleme sein soll, das hilft mir aber null weiter. Wie bestimme ich denn die Größe eines Unterproblems?

Vielleicht kann mir das ja jemand anhand des Fibonacci-Algorithmus erklären?
Code:
 int fib(int n)
    {
    if (n <= 2) return 1
    else return fib(n-1) + fib(n-2)
    }
 

yeha

Mitglied
Also wenn ich es richtig verstanden habe, ist a gleich 1, da es nur einen rekursiven Aufruf gibt, b müsste gleich 2 sein? und f(n)?
 

yeha

Mitglied
okay f(n) müsste 1 sein. damit hätte ich T(n/2)+1 und laut mastertherorem wäre die Laufzeit dann O(n^log2(1)) und das wäre doch n^0 also O(1) xD
 

Nuiton

Bekanntes Mitglied
Das Mastertheorem kannst du fuer dieses Beispiel nicht benutzen, da die Gleichung in der Form von
T(n) = aT(n/b) + f(n) sein muss.

1
. if (n <= 2) return 1
2. else return fib(n-1) + fib(n-2)

T(n) = O(1) + T(n-1) + T(n-2)
oder
T(n) = T(n-1) + T(n-2) + O(1)

Wir nehmen an das T(n-1) = O(2^(n-1)). Es folgt T(n) = O(2^(n-1)) + O(2^(n-2)) + O(1) = O(2^n).
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
T code so schreiben das er von sich selber anpasst (code soll die anzahl aller bustaben bestimmen) Java Basics - Anfänger-Themen 16
J Array Median bestimmen Java Basics - Anfänger-Themen 6
S Array Maximum bestimmen mit for und foreach Java Basics - Anfänger-Themen 7
J Array Mittleren Wert bestimmen Java Basics - Anfänger-Themen 2
M Radius von einer ellipse bestimmen Java Basics - Anfänger-Themen 7
Distanz zwischen zwei Zeichenfolgen in einem String bestimmen Java Basics - Anfänger-Themen 5
rosima26 Java SubSum bestimmen Java Basics - Anfänger-Themen 76
M Ersten Index von Array bestimmen Java Basics - Anfänger-Themen 14
C Kollision zweier Rechtecke, Schnittpunkte bestimmen Java Basics - Anfänger-Themen 25
C Boolesche Formel, Belegungen bestimmen Java Basics - Anfänger-Themen 8
Der Grütz Verständnisfrage zu Übung aus Java Kurs - Schaltjahr bestimmen Java Basics - Anfänger-Themen 2
H Den Wert einer rekursiven Funktion bestimmen Java Basics - Anfänger-Themen 5
L Partitionierungsgruppen bestimmen Java Basics - Anfänger-Themen 22
H Klassen Die Länge einer Text-Node bestimmen Java Basics - Anfänger-Themen 2
H Minimum in einem Array bestimmen Java Basics - Anfänger-Themen 7
Kawastori Größe eines Arrays bestimmen Java Basics - Anfänger-Themen 13
L Datentypen Deklarierte Felder einer Generic Klasse bestimmen Java Basics - Anfänger-Themen 7
M Array Summe bestimmen? Java Basics - Anfänger-Themen 14
N Bereich Zufallszahl bestimmen (50 und 100 / 80 und 90) Java Basics - Anfänger-Themen 2
J Y-Koordinate von GUI-Objekt bestimmen Java Basics - Anfänger-Themen 2
J Java GUI- Objekte Position per Quelltext bestimmen Java Basics - Anfänger-Themen 4
L Anzahl der Aufrufe von Schleifen bestimmen Java Basics - Anfänger-Themen 1
F Summe in einem Array bestimmen Java Basics - Anfänger-Themen 3
H Ersten Zug bestimmen Java Basics - Anfänger-Themen 12
O Suchbaum Elternknoten finden Level eines Knoten bestimmen Java Basics - Anfänger-Themen 24
C Kleinsten Kreis einer Punktmenge bestimmen Java Basics - Anfänger-Themen 4
CptK Methoden Koordinaten relativ zur Rotation eines Bildes bestimmen Java Basics - Anfänger-Themen 8
J Breite eines Strings bestimmen Java Basics - Anfänger-Themen 4
E Maximalwert im Array bestimmen Java Basics - Anfänger-Themen 8
L Datentypen Date API - diese Woche bestimmen Java Basics - Anfänger-Themen 1
Y Teile und Herrsche, längstes absteigendes Teilarray bestimmen Java Basics - Anfänger-Themen 12
T Min und Max einer Zahlenfolge bestimmen Java Basics - Anfänger-Themen 7
V Klassen Bestimmen Sie die erste und letzte Position an der ein 'c' steht? Java Basics - Anfänger-Themen 3
M Bestimmen, wie oft ein Char in einem Array vorkommt Java Basics - Anfänger-Themen 2
P Rückgabewert bestimmen Java Basics - Anfänger-Themen 17
C Vererbung - Ausgaben bestimmen Java Basics - Anfänger-Themen 6
T Anzahl bestimmter Werte eines arrays bestimmen Java Basics - Anfänger-Themen 4
G Datentypen Tipps, Ratschläge erwünscht bzgl. Datentyp bestimmen über Wertebereich Java Basics - Anfänger-Themen 5
E Summe der "Nachbarn" eines Wertes in einem Array bestimmen Java Basics - Anfänger-Themen 8
H Quotient durch Subtraktion bestimmen Java Basics - Anfänger-Themen 12
1 Größe einer zirkulären Liste bestimmen .. ? Java Basics - Anfänger-Themen 2
1 Minimum aller Elemente in einem Array bestimmen Java Basics - Anfänger-Themen 10
D Wochentag für eingegebenes Datum bestimmen anhand von Formel Java Basics - Anfänger-Themen 2
C Werteraum für Variable bestimmen Java Basics - Anfänger-Themen 5
S Vererbung exaktes "Objekt" der Unterklasse bestimmen Java Basics - Anfänger-Themen 5
Screen Wie geringste Absolutdifferenz zum Median bestimmen? Java Basics - Anfänger-Themen 8
V Aufrufendes Objekt bestimmen (nicht die Klasse) Java Basics - Anfänger-Themen 3
J Note bestimmen Java Basics - Anfänger-Themen 13
P BitSet- Objekt- Anzahl der Elemente bestimmen Java Basics - Anfänger-Themen 2
T Minimumsnorm bestimmen Java Basics - Anfänger-Themen 19
T String - kleinstes Zeichen bestimmen Java Basics - Anfänger-Themen 3
M bestimmen zu welchem Array ein Objekt "zugehört" Java Basics - Anfänger-Themen 5
L Koordinaten bestimmen Java Basics - Anfänger-Themen 8
S Zeit bestimmen Java Basics - Anfänger-Themen 4
H Anzahl Ziffer in Zahl bestimmen Java Basics - Anfänger-Themen 3
S Kleinster Wert im Array bestimmen Java Basics - Anfänger-Themen 4
J Klickposition genau bestimmen Java Basics - Anfänger-Themen 12
J Bestimmen ob String aus Kleinbuchstaben besteht Java Basics - Anfänger-Themen 16
N aktuelle Datum Mikrosekunden genau bestimmen Java Basics - Anfänger-Themen 8
G zweitgrößter Wert in array bestimmen Java Basics - Anfänger-Themen 4
L Farbe unter Cursor bestimmen Java Basics - Anfänger-Themen 5
T Variable aus dem Web Netz Internet URL bestimmen Java Basics - Anfänger-Themen 13
B Anzahl der Werte bestimmen Java Basics - Anfänger-Themen 14
F komplexität bestimmen Java Basics - Anfänger-Themen 10
X Anzahl Baumknoten bestimmen Java Basics - Anfänger-Themen 5
J Mouseposition bestimmen Java Basics - Anfänger-Themen 5
F Meßwertfolge bestimmen Java Basics - Anfänger-Themen 10
J Arraylänge mittels "Array.getLength" bestimmen!? Java Basics - Anfänger-Themen 3
B JMenu Position bestimmen Java Basics - Anfänger-Themen 7
H Javacode erklären: Mittelpunkt bestimmen Java Basics - Anfänger-Themen 4
M Interval Teilmenge bestimmen - Fehler in meiner Lösung Java Basics - Anfänger-Themen 6
N zweidimensionales array größe bestimmen Java Basics - Anfänger-Themen 1
A Anzahl Zeilen eines Arrays bestimmen Java Basics - Anfänger-Themen 10
Q Zeichnen - wie von außen bestimmen, was gezeichnet werden soll? Java Basics - Anfänger-Themen 26
J Classpath bestimmen, unter Windows 7 Java Basics - Anfänger-Themen 2
S Variable über den Vektor bestimmen Java Basics - Anfänger-Themen 20
A OOP Programm zum bestimmen von Primzahlen, OutofBoundsException Java Basics - Anfänger-Themen 10
B Anzahl von gerundeten Punkten bestimmen Java Basics - Anfänger-Themen 9
C Polygon um Figur bestimmen Java Basics - Anfänger-Themen 10
L Zeilenanzahl bestimmen? Java Basics - Anfänger-Themen 7
M Sha256-Wert eines Files bestimmen Java Basics - Anfänger-Themen 13
T aus Integer Array Maximum bestimmen Java Basics - Anfänger-Themen 7
M Nachbar von Knoten bestimmen Java Basics - Anfänger-Themen 8
J 2Dimensionales Array, Größe durch Eingabe bestimmen Java Basics - Anfänger-Themen 9
C Position eines Fensters bestimmen Java Basics - Anfänger-Themen 3
Y Vor- und Nachkommawerte eines doubles bestimmen Java Basics - Anfänger-Themen 7
W Variablenzuweisung über Wert bestimmen Java Basics - Anfänger-Themen 2
G die Größe eines Button bestimmen ? Java Basics - Anfänger-Themen 4
6 Wie das angeklickte Objekt bestimmen? Java Basics - Anfänger-Themen 4
philipp Instanznamen mit einem String bestimmen. Java Basics - Anfänger-Themen 11
P Abstand vom Rahmen zu Komponenten bestimmen? Java Basics - Anfänger-Themen 3
kulturfenster User soll Radius von Kugel bestimmen Java Basics - Anfänger-Themen 4
W Letzten beiden Ziffern eines BigIntegers bestimmen? Java Basics - Anfänger-Themen 20
G Dateigröße bestimmen Java Basics - Anfänger-Themen 2
B Länge eines Char-Arrays bestimmen Java Basics - Anfänger-Themen 7
S Anzahl von zeilen einer Datei bestimmen. Java Basics - Anfänger-Themen 4
B Position einer Ziffer im String bestimmen Java Basics - Anfänger-Themen 4
X Klasse eines Objektes bestimmen Java Basics - Anfänger-Themen 2
G Objektname über Eingabe bestimmen Java Basics - Anfänger-Themen 4
0 Häufigste(n) Zahl(en) in zweidimensionalem Array bestimmen ? Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben