laufzeitberechnung - untere schranke
-
hallo, angenommen ich habe eine laufzeitabschätzung
dann ist . aber was kann ich über Ω aussagen? ist das der am langsamsten wachsende term in der abschätzung? (hier also c = konstant).
dankeschön
k
-
Das kann man so nicht sagen. Wenn die Laufzeit fest ist, also T(n) = 2^n + n^2+n+c, dann ist das in Omega(2^n).
Zumeist schaut man sich aber die worst-case-Laufzeiten an: T_max(n) = O(...). Dann hängt Omega aber davon ab, wie der Algorithmus konkret aussieht. Braucht er in gewöhnlichen Fällen 2^n + n^2 + n + c. Aber in einigen Fällen isser schon in Linearzeit fertig? Dann ist er in Omega(n).
Wichtig ist hier auch die Unterscheidung, ob Du die Funktion T(n) abschätzen willst? Die ist in Theta(schnellst wachsendes Teil), oder ob Du nen Algorithmus betrachtest und dessen Laufzeit für alle Fälle von unten beschränken willst.
-
angenommen ich habe keinen algorithmus sondern nur die laufzeit (un-)gleichung.
kann ich dann nur aussagen ? eigentlich schon, oder? ich kenne ja worst/best case gar nicht und solche gleichungen berücksichtigen das ja auch nicht...
danke dir!