Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Suche » Suchergebnis » Hallo Gast [Anmelden|Registrieren]
Zeige Beiträge 1 bis 1 von 1 Treffern
Autor Beitrag
Thema: Komplexitätsklasse, n0 und Konstante c bestimmen
HansWurst

Antworten: 0
Hits: 1.285
Komplexitätsklasse, n0 und Konstante c bestimmen 22.09.2020 11:25 Forum: Berechenbarkeits- und Komplexitätstheorie


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
Zeige Beiträge 1 bis 1 von 1 Treffern