Zeitkomplexität Algorithmen |
| 30.03.2017, 12:33 | Auf diesen Beitrag antworten » |
| saniker | 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. |
|
|
|
| 08.04.2017, 08:22 | Auf diesen Beitrag antworten » |
| skubidoo09 | 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 |
|
|
