HansWurst
Grünschnabel
Dabei seit: 22.09.2020
Beiträge: 1
 |
|
| Komplexitätsklasse, n0 und Konstante c bestimmen |
     |
Hallo,
die Funktion f(n) = 3n^2 - 6n + 9 liegt ja in der Komplexitätsklasse n^2 (n Quadrat), da ich ein c und ein n0 finde, für die 3n^2 - 6n + 9 <= cn^2 gilt
(für ein c und alle n > n0)
Ich wollte nun, beispielhaft konkrete Konstanten c ermitteln und Zahlen n0 für die die o.g. Gleichung erfüllt ist.
Stelle ich nun 3n^2 - 6n + 9 <= cn^2 um, komme ich (Division mit n^2) auf:
3 - 6/n + 9/n^2 <= c
Wähle ich also n=1 dann ist c >= 6, es gibt also ein n0 (hier 1) und ein c (hier 6) so das für alle n > n0 die Gleichung gilt
Analog kann ich auch für n = 1,5 bzw. 3/2 argumentieren.
Wähle ich also n=1,5 dann ist c >= 3 usw.
Es gilt also
f(n) <= 3n^2 für alle n > 1.5
Was ich jedoch nicht verstehe, vielleicht habe ich mich da auch verrechnet:
Wähle ich nun n=2 und setze dies in die o.g. Gleichung ein,
dann ist ja c >= 2,25 da
3-6/2 + 9/2^2 <= c
3-6/2 + 9/4 <= c
3-3+2.25 <= c
2.25 <= c
Wähle ich jedoch c=2.25 und n0=2 dann gilt das jedoch nicht für alle n>2. Beispiel:
f(n) = 3n^2 - 6n + 9 und g(n) = 2.25n
f(n) <= g(n) gilt hier eben NICHT mehr für alle n0 > 2 und c = 2.25, da ab f(7) und g(7) f(n) <= g(n) eben nicht mehr gilt
f(0) = 9, g(0) = 0
f(1) = 6, g(1) = 2.25
f(2) = 9, g(2) = 9
...
f(6) = 81, g(6) = 81
f(7) = 114, g(7) = 110,25
3n^2 - 6n + 9 <= 2.25n^2 klappt also nicht, obwohl ich die o.g. Konstanten durch einsetzen von n=1 und n=1.5 ja so ermitteln konnte.
WARUM SIND DIE WEITER OBEN ERMITTELTEN KONSTANTEN UND n0 (c=6, n0=1 und c=3, n0=1.5) KORREKT, WÄHREND c=2.25 und n0=2 SO JEDOCH NICHT MEHR FUNKTIONIEREN, WENN ICH n=2 EINSETZE?
Gruß und Danke
|
|
