 Zeitkomplexität Algorithmen |
saniker
Grünschnabel
Dabei seit: 30.03.2017
Beiträge: 1
 |
|
| 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.
|
|
30.03.2017 12:33 |
|
|
skubidoo09
Grünschnabel
Dabei seit: 08.04.2017
Beiträge: 8
|
|
| 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
|
|
|
08.04.2017 08:22 |
|
|
|
