Komplexitätsklasse, n0 und Konstante c bestimmen |
22.09.2020, 11:25 | Auf diesen Beitrag antworten » |
HansWurst | 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 |
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|