O-Notation

[raktion]

Hallo!

Ich habe hier eine Aufgabe und weiss nicht so ganz, ob ich das richtig vertanden habe:

Gegeben folgende Java Methode m(n):

sum = 0;
bound = f(n);
    for (int i = 0; i < bound; i++) {
        for (int j = n; j >= 0; j--) {
            sum += (i + 2 * j);
        }
    }

Geben sie einfache und gute O-Schranken für die Laufzeit von m(n) unter folgenden Annahmen:

Die Laufzeit von f(n) ist O(n!) und der Wert von f(n) ist 2^n.


Also ich habe mir bisher folgendes gedacht:

sum = 0;    // O(1)  --> Zuweisung
bound = f(n);       // O(1)  -->Zuweisung
    for (int i = 0; i < bound; i++) {   // O(2^n)   --> Wert von f(n)
        for (int j = n; j >= 0; j--) {   // O(n)    --> n Durchläufe
            sum += (i + 2 * j);     // O(1)   
        }
    }

In der Summe müsste das doch O(n*2^n) sein, was mich hier etwas irritiert ist die Laufzeit von f(n) = O(n!) muss ich das berücksichtigen bei der Zuweisung:

bound = f(n);

Ich hoffe jemand hat da etwas Ahnung von und könnte mir kurz erläutern, ob ich das so richtig gemacht habe bzw. wenn nicht, wo meine Fehler liegen. Danke schonmal!

 

[HimBromBeere]

Kannst dir mal das hier ansehen, da geht´s auch um die Notation:
http://www.java-forum.org/java-basics-anfaenger-themen/131011-schleifen-o-notation.html

 

[raktion]

Hi!

Danke, aber das habe ich mir durchgelesen und kann die Antworten da nicht auf mein Problem übetragen, mir gehts um dieses "Die Laufzeit von f(n) ist O(n!)..." Inwieweit das zu berücksichtigen ist...

 

[XHelp]

Deine Laufzeit ist nicht vollständig. Wenn f(n) noch zusätzlich eine Laufzeit hat, dann musst du die natürlich auch dazurechnen.
Wenn du dann eine gesamte Laufzeit hast, kannst du dir überlegen, wie du diese vereinfachen kannst, dazu gibt es bei O-Notationen einige Regeln.

 

[HimBromBeere]

Deine Gesamtlaufzeit ergibt sich über:

t(f(n) + t(g(i) mit i = 0 .. bounds

t(g(i)) widerum hat eine Laufzeit t = t(bounds * n) = O(n^2)

woraus sich ergibt:

t = O(n!) + O(n^2)

EDIT: Dein Fehler (nebem dem Vergessen der Laufzeit von f(n)) ist, dass

O(n*2^n)

nicht die Laufzeit der For-Schleife ist. Die äußere Schleife hat O(bounds), die innere hat O(n), also zusammen

O(bounds * n) oder O(n^2) mit bounds ungefähr gleich n

 

[raktion]

hi!

Vielen dank schonmal für die Ausführungen, aber das verstehe ich iwie immer noch nicht, sorry.

O(bounds) ist doch gleich O(2^n) oder nicht?

Und wenn ich die Laufzeit von f(n) noch dazunehme also O(n!) dann würde diese laufzeit doch für m(n) auch gelten oder? Weil n! doch schneller wächst als 2^n. Oder stehe ich da jetzt auf dem Schlauch.

Bei dir steht immer n^2, ich meine allerdings 2^n...

 

[HimBromBeere]

Wie kommst du auf O(2^n)?! Hast du

Die äußere Schleife hat O(bounds), die innere hat O(n), also zusammen O(bounds * n) oder O(n^2)

gelesen?

Die äußere Schleife wird bounds-mal ausgeführt, die innere n-mal. Also wird die innere Schleife

bounds * n

mal ausgeführt...

EDIT: Aaaah, jetzt hab ich´s gefunden, die Funktion f = 2 ^ n. Was das mit dem Ganzen zu tun hat, seh ich grade nicht... da würde´s drauf ankommen wie die Funktion f implementiert wurde.

 

[XHelp]

Die Laufzeit von f(n) ist O(n!) und der Wert von f(n) ist 2^n.

wie kommst du da auf die Aussage:

also zusammen O(bounds * n) oder O(n^2) mit bounds ungefähr gleich n

:bahnhof:

O(n!+n*2^n) ist übrigens in O(n!)

 

[HimBromBeere]

Hab auch nix anderes behauptet:

t = O(n!) + O(n^2)

Da fehlt nur das Ergebnis der Addition... und mit dem hast du natürlich Recht, das ist O(n!)




EDIT: Oooooooh, hab´s endlich gefunden... die bounds werden über f(2^n) berechnet... daher der Anstieg an Laufzeit... in dem Fall ist natürlich die Ordnung nicht n^2 sondern, wie ihr bereits erkannt habt, n*(2^n)...

An der Gesamtlaufueit ändert dies allerdings wenig, die ist und bleibt n!

 

[XHelp]

??? O(2^n) ist doch bei weitem nicht in O(n). Das eine ist exponentiell, das andere ist linear. Da kannst du nicht

bounds

mit "so ungefähr n" abschätzen.

 

[HimBromBeere]

Das eine ist exponentiell, das andere ist linear. Da kannst du nicht bounds mit "so ungefähr n" abschätzen.

Ja, ist mir ja jetzt auch aufgefallen...
Das heißt aber auch, dass in diesem speziellen Fall das Berechnen der Summe in der Schleife schneller geht als Berechnen der Grenzen dieser Schleife... tja, sieht man auh nicht alle Tage 😀

 

[raktion]

Oh hier hat sich ja was getan 🙂

Okay dann lag ich doch nihct ganz so falsch wir hatten nur ein kleines verständnisproblem 🙂

Vielen dank euch, jetzt hab ichs und kann die restlichem Aufgaben angehen.