---

Geschrieben von saniker am 30.03.2017 um 12:33:

  Zeitkomplexität Algorithmen

Meine Frage:
Ich hätte paar Fragen zur Zeitkomplexität von Algorithmen. Ich versteh nicht so ganz wie man eine Funktion zu einer der 3 Möglichkeiten zuordnet. Da gäbe es groß O, Omega und Theta. Die Formeln kenne ich auch. Nur weiß ich nicht was das c in der Formel sein soll. und woher ich g(n) bekomme.
Als Beispiel hätte ich: f(n)= 3n^2+30n+300. Wie finde ich jetzt g(n) ?
Zu dem Beispiel: Ich könnte mein c und mein g(n) so wählen das die Formel der oberen und der unteren Schranke aufgeht, aber das ist ja nicht Sinn der Sache

Meine Ideen:
Soweit ich weiß sucht man sich n und g(n) aus der Formel selbst aus, doch dann kann ich es so wählen das die Funktion für die obere und die untere Schranke gilt.

---

Geschrieben von skubidoo09 am 08.04.2017 um 08:22:

  RE: Zeitkomplexität Algorithmen

Hi,

Du musst die Asymptote für f(n) bestimmen. Versuch es argumentativ: Da f(n) stetig steigt (quadratischer + linearer Term), lässt sich keine LINEARE Asmyptote als Ober- oder Untergrenze finden. Du könntest als Asymptote g(n) = f(n) verwenden, aber asymptotisch ist das witzlos. O(f(n)) wäre dann auch f(n), was Sinn macht wegen der stetigen Steigung.

Grüße

Sascha