Hallo Zusammen,
ich studiere Informatik(2 Semester) und habe vor ein paar
Tagen eine Aufgabe bekommen, die ich nicht läsen kann.
"Ermitteln Sie möglichst gute (enge) Komplexitätsmaße in
O-Schreibweise für die folgenden rekursiv definierten Funktionen
T(n), die natürliche Zahlen >0 auf natürliche Zahlen abbilden:
a)
T(1) = 1
T(n) = T(n-1) + n für n > 1
b) …
c) …"
Könnte mir jemand vielleicht anhand dieser Aufgabe erklären, wie ich zu
einer Lösung komme. Habe auch schon im google.de nachgeschaut und
nichts vernünftiges gefunden.
Ich hoffe Sie können mir helfen 
Danke
gruß
Sergej
Hallo,
T(n), die natürliche Zahlen >0 auf natürliche Zahlen
abbilden:
a)
T(1) = 1
T(n) = T(n-1) + n für n > 1
b) …
c) …"
Könnte mir jemand vielleicht anhand dieser Aufgabe erklären,
wie ich zu
einer Lösung komme
Wenn du erst mal keine Ahnung hast, probier einfach die ersten paar Glieder der Kette auszurechnen:
T(1) = 1
T(2) = T(1) + 2 = 3
T(3) = T(2) + 3 = 6
T(4) = T(3) + 4 = 10
T(5) = T(4) + 5 = 15
T(6) = T(5) + 6 = 21
So, und jetzt plottest du dir mal die Werte. Dann siehst du schon, welche Abhängigkeit das hat.
Tatsächlich kann man das noch ein bisschen weiter zerlegen:
T(1) = 1
T(2) = 1 + 2
T(3) = 1 + 2 + 3
T(4) = 1 + 2 + 3 + 4
Und dafür schaffst du es ja wohl eine Formel anzugeben 
Grüße,
Moritz
Hallo Moritz,
das habe ich verstanden. Vielen Dank.
Dann wäre die Formel wäre dann O(n), weil der Wert immer um n sich ändert.
Und wenn ich diese Aufgabe hätte:
T(1) = 1
T(n) = 2⋅T(n–1) für n > 1
Lösung:
T(1) = 1
T(2) = 2 * T(1) = 2
T(3) = 2 * T(2) = 4
T(4) = 2 * T(3) = 8
T(5) = 2 * T(4) = 16
=> O((2^(n-1))/2)
Wäre das richtig?
Wie kann man die Formel am einfachsten rausfinden?
Danke
gruß
Sergej
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
das habe ich verstanden. Vielen Dank.
Dann wäre die Formel wäre dann O(n), weil der Wert immer um n
sich ändert.
Für die O-Notation interessiert aber nicht, wie sich der Wert ändert, sondern was der wert ist.
Und wenn ich diese Aufgabe hätte:
T(1) = 1
T(n) = 2⋅T(n–1) für n > 1
Lösung:
T(1) = 1
T(2) = 2 * T(1) = 2
T(3) = 2 * T(2) = 4
T(4) = 2 * T(3) = 8
T(5) = 2 * T(4) = 16
=> O((2^(n-1))/2)
Wäre das richtig?
Wie kommst du auf 2^(n-1)/2 ? wenn du da mal 1 einsetzt, kommst du auf 2^(1-1)/2 = 1/2, das ist nicht 1.
Aber bei der O-Notation interessieren konstante Faktoren sowieso nicht, also kannst du einfach O(2^n) schreiben, da das das gleiche ist wie O(2^(n-1))
Wie kann man die Formel am einfachsten rausfinden?
Sach mal, lernt ihr das nicht? Normalerweise sind doch die Übungsaufgaben an die Vorlesungen angepasst.
Grüße,
Moritz