+1 Daumen
144 Aufrufe

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.

Ein Beispiel wäre echt super.

von

1 Antwort

0 Daumen

Hallo hj2455, mir ist leider unklar, was du mit c meinst. 
Zu deiner Frage:  Es gilt
f = O(g)   <=>   lim |f(x)/g(x)| < ∞
Quelle:  z. B. Wikipedia „Landau-Symbole“
Beispiel:  f(x) = 5 * x^2 + 2 * x + 8 = O(x^2)   
Mit Omega und Theta kenne ich mich leider nicht aus.

von 3,5 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
0 Antworten

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community