4. Komplexitätstheorie

Komplexitätstheorie

  • S

    Morgen,

    ich habe eine Frage zu einer Aufgabe zur Komplexitätstheorie.

    Die Aufgabe sei folgende:
    f(n)=n100f(n) = n^{100}
    g(n)=2n100g(n) = 2^{\frac{n}{100}}
    Man zeige, dass entweder f=o(g)f = o(g), g=o(f)g = o(f) oder f=Θ(g)f = \Theta (g).
    Falls tatsächlich f=o(g)f = o(g), soll man das erste n finden für welches f(n)<g(n)f(n) < g(n) gilt.

    Meine Überlegung ist folgende.

    Wenn man n verdoppelt, dann steigt f um den Faktor 21002^{100}:
    (2n)100=2100∗n100(2n)^{100} = 2^{100} * n^{100}
    Also eine Konstante.

    Während g um den Faktor 2n1002^{\frac{n}{100}} steigt:
    22n100=22n100=(2n100)2=2n100∗2n1002^{\frac{2n}{100}} = 2^{2\frac{n}{100}} = (2^{\frac{n}{100}})^2 = 2^{\frac{n}{100}} * 2^{\frac{n}{100}}
    also um einen von n abhängigen Wert. Das heißt, der Faktor wird bei n>10000n > 10000 größer als der von f, und das führt dazu dass g f irgendwann komplett überholen wird und die Differenz zwischen g(n) und f(n) auch immer größer wird.
    Für jede Konstante c wird es dann ein n geben, für welches cg(n)≥f(n)c g(n) \ge f(n).

    Das erste N, für welches g(n)>f(n)g(n) > f(n) muss ich noch finden. Aber ist der Beweis so richtig?

    0
  • K

    Das sind nur Ueberlegungen aber kein Beweis. Benutze die die Definitionen!

    0
  • S

    knivil schrieb:

    Das sind nur Ueberlegungen aber kein Beweis.

    Habe ich mir gedacht. Zu informal...

    Benutze die die Definitionen!

    Welche Definitionen? Die von der Big-Oh Notation?

    0
  • J

    Sone schrieb:

    knivil schrieb:

    Das sind nur Ueberlegungen aber kein Beweis.

    Habe ich mir gedacht. Zu informal...

    Benutze die die Definitionen!

    Welche Definitionen? Die von der Big-Oh Notation?

    Wohl eher die vom kleinen o... Dadrüber willst du schließlich was sagen.

    0
  • S

    Jester schrieb:

    Wohl eher die vom kleinen o... Dadrüber willst du schließlich was sagen.

    Das meinte ich ja. Im Buch wird halt alles unter dem Oberbegriff Big-Oh Notation zusammengefasst.

    Zu beweisen wäre:
    Für jedes ϵ > 0 gibt es ein n0n_0, für welches gilt:
    ∀n≥n0  ϵg(n)≥f(n)\forall n \ge n_0 ~~ \epsilon g(n) \ge f(n)

    Gut, folgendes gilt:
    f(xn)=f(x)f(n)f(xn) = f(x) f(n) . Beweis:
    f(xn)=(xn)100=x100∗n100f(xn) = (xn)^{100} = x^{100} * n^{100}
    Es gilt außerdem:
    g(xn)=g(n)xg(xn) = g(n)^x . Beweis:
    2xn100=2xn100=(2n100)x2^{\frac{xn}{100}} = 2^{x\frac{n}{100}} = (2^{\frac{n}{100}})^x

    Also
    f(n^2) = (f(n))²
    Und
    g(n2)=g(n)ng(n^2) = g(n)^n

    Hier komme ich nicht weiter.Wie zeige ich formal, dass dieses Steigungsverhalten zu etwas führt?

    0
  • S

    Außerdem scheinen meine Ergebnisse stark unintuitiv zu sein. Auch wenn laut meinen "Berechnungen" der große Schnittpunkt bei dem n liegt welches die Bedingung
    nlog2(n)=104\frac{n}{log_2(n)} = 10^4
    erfüllt...

    0
  • O

    Ich habe gerade das Gfühl, dass du gar nicht weißt, wie der Beweis auszusehen hat sondern nur irgendwelche Dinge in irgendwelche Funktionen einsetzt.

    Tipp: nimm die Definition, wähle ein beliebiges epsilon und berechne dann einfach für welche n die Ungleichung gilt. Alternativ kannst du dir auch die Definition der e-Funktion anschauen, falls ihr die schon hattet.

    //edit ich verstehe auch gerade nicht, was du da als unintuitiv erachtest.

    0
  • S

    otze schrieb:

    //edit ich verstehe auch gerade nicht, was du da als unintuitiv erachtest.

    Den Fakt, dass n100n^{100} durch 2n/1002^{n/100} überholt wird. Plotte die Graphen, dann siehst du was ich meine.

    Ich habe gerade das Gfühl, dass du gar nicht weißt, wie der Beweis auszusehen hat sondern nur irgendwelche Dinge in irgendwelche Funktionen einsetzt.

    Deswegen frage ich ja hier. 🤡

    Tipp: nimm die Definition, wähle ein beliebiges epsilon und berechne dann einfach für welche n die Ungleichung gilt.

    Gute Idee. Hatte ich irgendwie schon.

    Alternativ kannst du dir auch die Definition der e-Funktion anschauen, falls ihr die schon hattet.

    "Ihr"? Wieso ihr? Ich bringe mir das hier gerade selbst durch
    Computational Complexity | ISBN: 0521424267
    bei...

    0
  • S

    Wo ich konkret nicht weiter komme, ist bei dieser Ungleichung:
    n100<2n100n^{100} < 2^{\frac{n}{100}}
    log2(n100)<n100log_2( n^{100} ) < \frac{n}{100}
    100∗log2(n)<n100100 * log_2( n ) < \frac{n}{100}
    105∗log2(n)<n10^5 * log_2( n ) < n
    Wie soll ich das auflösen?

    0
  • M

    100 * 100 = 10^4. Lösen kannst du mit der Lambert-W-Funktion.

    0
  • S

    Michael E. schrieb:

    100 * 100 = 10^4.

    Falsch eingetippt. 🙂

    Danke für den Tipp, ich setz' mich dran.

    0
  • O

    der tipp bringt dir nichts. Studenten lösen die Aufgabe ohne Lambert-W. Hier musst du einfach schätzen, ab wann das gilt. Also einfach mal ein bliebig großes N einsetzen.

    Und Nein, das Ergebnis ist nicht unintuitiv. plotte das Ergebnis mal für sehr große N.

    //edit zum ersten Punkt: du musst nur ein n_0 finden, für welches die Aussage gilt, nicht das Kleinstmögliche. Dafür bräuchtest du in der Tat Lambert-W.

    0
  • S

    otze schrieb:

    du musst nur ein n_0 finden, für welches die Aussage gilt, nicht das Kleinstmögliche. Dafür bräuchtest du in der Tat Lambert-W.

    Sone schrieb:

    Falls tatsächlich f=o(g)f = o(g), soll man das erste n finden für welches f(n)<g(n)f(n) < g(n) gilt.

    🙂 👍

    Auch wenn Lambert-W hier nicht trivial anwendbar ist, wie es scheint.

    Aber eigentlich sollte n doch eine natürliche Zahl sein, oder?

    0
  • J

    Jetzt mach erstmal schritt 1 und dann schritt 2. schreibe mal genau hin was du beweisen musst...

    0
  • S

    Das habe ich schon längst!
    Zu beweisen wäre:
    Für jedes ϵ > 0 gibt es ein n0n_0, für welches gilt:
    ∀n≥n0  ϵg(n)≥f(n)\forall n \ge n_0 ~~ \epsilon g(n) \ge f(n)

    Die Idee ist nun, wie otze schon gesagt hat, die Ungleichung zu lösen. Ich harke nun wie gesagt an Lambert-W...

    0
  • B

    Es ist manchmal wesentlich einfacher, zu zeigen, dass eine Lösung existiert, als diese anzugeben...

    0
  • S

    Ja, aber ich muss die Lösung doch zeigen! Ich muss das kleinste n angeben, für welches diese Ungleichung erfüllt ist!
    Mir ist durchaus klar, dass ich mir sonst unnötigen Aufwand antun würde. Ich habe die Überlegung schon im OP dargelegt, mit der ich nur zeigen wollte dass es eine Lösung gibt.

    Ich denke aber, dass n eine natürliche Zahl ist, da schließlich die Funktionen die Länge der Eingabe als Parameter nehmen sollten. Daher wird das sehr schnell gefunden sein. Aber ich würde trotzdem gerne auch die reelle Lösung haben. Um Lambert-W zu verstehen. 🙂

    0
  • J

    Jetzt mach doch erstmal den ersten beweis fertig. Und vergiss das W. Das ist doch nur ein "kann funktion nicht umkehren, also geb ich der umkehrfunktion halt nen namen und rechne damit weiter"

    0
  • S

    Jester schrieb:

    Jetzt mach doch erstmal den ersten beweis fertig. Und vergiss das W. Das ist doch nur ein "kann funktion nicht umkehren, also geb ich der umkehrfunktion halt nen namen und rechne damit weiter"

    Ja, aber ich komme hier nicht weiter:

    n100<ϵ2n100n^{100} < \epsilon 2^{\frac{n}{100}}
    Davon habe ich leider nichts. Ich kann das Umformen wie ich will, aber ...

    Ein Ansatz wäre folgendes:

    n1002n100<ϵ\frac{n^{100}}{2^{\frac{n}{100}}} < \epsilon
    Nun ist zu beweisen, dass der Bruch für n → ∞ gegen Null läuft - und damit zwangsläufig auch unter →.
    Also in anderen Worten, dass der Nenner größer und größer als der Zähler wird.

    Im OP habe ich schon eine Überlegung geäußert - man verdoppelt das Funktionsargument, und zeigt, dass ab n > 10000 der Faktor beim Nenner größer wird. Und dieser dadurch immer schneller steigt als der Zähler.
    Da wenn eine Funktion f schneller steigt als eine Funktion g, f diese zwangsläufig überholen und die Differenz gegen ∞ geht... reicht das aber alles für einen Beweis?
    Ich kann dann zeigen, dass für jedes ε ab einem bestimmten n das Verhältnis von g zu f groß genug ist, sodass die Ungleichung erfüllt ist.

    0

  • Ohne den Thread ganz genau gelesen zu haben: Du kannst beide Seiten einer Ungleichung durch eine stetig streng monoton steigende Funktion schicken und die Ungleichung hält immer noch. Alle Werte sind strikt positiv; ich schlage den Logarithmus zur Basis 2 vor...

    Alternativ könntest du auch mit der Definition über den Limes arbeiten. Dort könnte das hilfreich sein: http://de.wikipedia.org/wiki/Regel_von_L’Hospital

    0
  • S

    Ja, das war ein guter Tipp!
    100 mal ableiten ergibt:

    100!(ln2100)1002n100\frac{100!}{ (\frac{ln 2}{100})^{100} 2^{\frac{n}{100}} }

    Und da dieser Bruch konvergiert (für x → ∞ läuft er gegen 0), ist die Regel anwendbar!

    Das heißt, damit habe ich eigentlich bewiesen, dass der Bruch gegen Null läuft. Un dass damit für jedes ε ein n existiert, welches dieser Ungleichung genügt...
    (Bzw. jetzt kann man es sehr leicht aufzeigen)

    0
Anmelden zum Antworten