Algorithmen O-Notation

Wissenschaft Informatik
#1

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 :smile:

Danke

gruß
Sergej

#2

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 :wink:

Grüße,
Moritz

#3

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]

#4

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