Unterschied O(n) und T(n)?
Ich verstehe nicht, was der Unterschied zwischen der O-Notation und der asymptotischen Laufzeit ist. Beide beschreiben die Abhängigkeit der Laufzeit zur Problemgrösse und lassen uns die Algorithmen in verschieden Klassen einteilen, aber was ist der Unterschied?
2 Antworten
ich meine das O(n) steht für die Komplexität an sich, also Anzahl-Schleifendurchläufe proportional zu n. Da kann je nach Art der Schleife schon auch etwas rauskommen was nicht genau Zeitlinear ist (z.B. weil die Speicheroperationen komplexer werden mit steigendem n).
T(n) wäre dann mehr praxisorientiert. Also wirklich Laufzeit.
Aber sicher bin ich da nicht. Nur mal so als Anregung.
T(n) ist eine Funktion, die die worst- oder average-case Laufzeit eines Algorithmus angibt. Man erhält für jedes n ein genaues Ergebnis.
O(f(n)) ist eine Klasse von Funktionen, welche die gleiche Komplexität wie f(n) haben.
Ein Beispiel:
T(n) = n² + 69n
Daraus folgt, dass T(n) in O(n²) liegt.
Ahaaa. O(n) ist also die Klasse und T(n) ist die asymptotische Laufzeit eines bestimmtes Algorithmus.