Problem(?) mit den O-Notationen

[Newbie111]

Hallo, ich soll die O-Notationen von ein paar Methoden angeben, jedoch komm ich allein bei den ersten 5 immer auf O(n)... kann natürlich sein, dass es so ist, aber fänd ich irgendwie zu einfach und bevor ichs falsch vorstelle frag ich lieber nochmal nach ^^

    static int a(int n){       

        int t=1, z=0;
        
        while (n>0){
            n -= t; t += 2; z++;
        }
        return z;
    }


    public static int b(int n){
       int i=0;
       int b=1;

       while(++i<n){
          b=b+2*i+1;
       }
       return b;
    }
	

    static int c(int n){

        int z=0;

        while (n>1){
            n/=2; z++;
        }
        return z;
    }


      static int d(int n){

          return a(b(n));
      }   
        

      static int e(int n){

           return b(a(n));
      }   


     static int f(int n){

       return a(c(n));
     }


     static int g(int n){

       return a(n) + c(n);
     }


      static int h(int n){

          return b(b(n));
      }
   

     static int i(int n){

        int z=0;
        int y=a(n);

        for(int i=1; i<=y; i++)

            z+=a(n);

        return z;
    }


    static int j(int n){

        int z=0;

        for(int i=1; i<=a(n); i++)

            z+=a(n);

        return z;
    }

 

[SlaterB]

so wie du fragst, kann man dir ja nur widersprechen, indem man richtige Lösungen vorgibt,
sagen wir es mal am wenigsten verratend: nein, nicht alle der ersten 5 sind O(n),

gib zu jeder eine Begründung, dann kann man die näher beurteilen

ansonsten der allgemeine Tipp:
prüfe, wieviele Hauptarbeitsschritte pro n durchzuführen sind,
hier kann man meist die Schleifendurchgänge zählen,

bei verketteten Methodenaufrufen beide Schleifen zusammenzählen

entscheidend ist im Grunde, ob es für n = 1000 um den Daumen 1000 Schleifendurchläufe sind (oder auch 500 oder 2000, auf einen konstanten Faktor kommt es nicht an),
oder eher deutlich unter 100 (log(n)?), oder auf einmal 100.000 und mehr (n^2 oder n * log(n)?)

 

[Marco13]

Hm. Einige der genannten Punkte könnten potentiell verwirrend sein: Bei verketteten Methodenaufrufen sollte man nicht "zusammenzählen" (im Sinne von "addieren"). WAS genau man von Fall zu Fall machen muss, kannst du dir vielleicht mit "Wikipedia Rechenregeln zu O-Notation" oder so zusammensuchen.

Und anhand EINER Durchlaufzahl kann man garnichts sagen - also, ob bei n=1000 nun 10 oder 10000000 Schleifendurchläufe gemacht werden, sagt nichts aus. Entscheidend ist die Frage, wie sich die Anzahl der Schleifendurchläufe ändert, wenn man n ändert (genau DAS beschreibt man ja mit der O-Notation). Du solltest dir also eher Fragen stellen wie:
"Wie ändert sich die Anzahl der Schleifendurchläufe wenn ich n um eins erhöhe, UND wie ändert sie sich, wenn ich n um zwei erhöhe?"
oder
"Wie ändert sich die Anzahl der Schleifendurchläufe, wenn ich n verdopple, UND wie ändert sie sich wenn ich n halbiere?" (das letzte war schon fast ein Tipp zu einer Lösung....). Beachte, dass das scheinbar jeweils zwei Fragen sind, sie aber zur Lösungsfindung jeweils genau so (mit dem "UND") gestellt werden müssen....

 

[Gast]

hmm, ok, ich seh schon, ich muss nochmal drüberschauen. aber wenn ich sowas wie 2n oder n/2 rausbekomme ist es doch trotzdem nur n, oder?

 

[SlaterB]

ja

----

Hm. Einige der genannten Punkte könnten potentiell verwirrend sein: Bei verketteten Methodenaufrufen sollte man nicht "zusammenzählen" (im Sinne von "addieren"). WAS genau man von Fall zu Fall machen muss, kannst du dir vielleicht mit "Wikipedia Rechenregeln zu O-Notation" oder so zusammensuchen.

hast du eine spezielle Seite im Blick?

unter
http://wedelwiki.de/index.php/Formelsammlung_O-Notation
steht ja nicht mal der Fall f(g(n)), ich wüßte aber nicht, was gegen 'zusammenzählen' spricht,
dass konstante Faktoren wie n + n = 2*n = n wegfallen muss man bis dahin eh kapiert haben, sonst geht alles schief

Und anhand EINER Durchlaufzahl kann man garnichts sagen [..]

klar, wenn irgendwo noch mit 100 mulitpliziert wird, dann hat man auch bei O(n) für n = 1000 auf einmal 100.000 Schritte,
aber solch konstante Faktoren sind ja nun wirklich zu erkennen und auch derart unnötig gemein, dass sie hier beispielsweise richtigerweise nicht auftauchen,

wenn man es also nicht übergenau nimmt kommt man mit dem einfachen Gedanken in 99% aller Fälle zum Ziel

 

[Marco13]

Ja, solche Rechenregeln meinte ich. Aber (Irrtümer vorbehalten: ) Wenn man sowas hat wie

f(n) { for (i=0..n) { ... } return n }
g(n) { for (i=0..n*n) { ... } return n*n }

dann hat man einmal O(n) und einmal O(n²). Sowas wie f(g(n)) oder g(f(n)) hat damit auch O(n²) (oder O(n²+n), was das gleiche ist) - aber das hängt ja vom Rückgabewert ab: Sowas wie

h(n) { return 2^n }

wäre zwar h € O(1), aber h(f(n)) wäre O(n) während f(h(n)) schon in O(2^n) wäre. Interessant wird's dann bei

i(n) { for (i=0..n) { g(n) }

Dort kann man die Komplexität von i nicht bestimmen, wenn man g nicht kennt - im Fall von obigem g wäre die Komplexität hier O(n^3)

Einfach "zusammenzählen" (oder beim ersten auch eine "Maximumsbildung") klingt vielleicht einfacher, als es ist...

 

[SlaterB]

> wäre zwar h € O(1), aber h(f(n)) wäre O(n) während f(h(n)) schon in O(2^n) wäre

was sich genau durch Zählen herausfinden läßt,
h(n) liefert 2^n, deshalb muss die Schleife in f 2^n mal durchlaufen werden
-> 2^n Schleifendurchläufe

ich schlage ja nicht vor, nur stumpf die Anzahl der Schleifen im Quellcode zu zählen
egal, ich war eben ungenau, da kann man alles mögliche hineininterpretieren

 

[Gast]

kann mir wenigstens einer sagen bei welcher methode zb nicht o=n ist? also von den ersten 5 jetzt. komm nämlich egal was ich mache immer auf max o(n). klar, evtl isses n o(log n) aber wie soll ich das beweisen???

 

[SlaterB]

c ist nicht O(n)

 

[Gast]

hmm, demnach kann es ja nur noch log n sein, weil mehr als n isses sicher nicht. aber woher weiss ich das?

 

[SlaterB]

entweder mit meiner 99%-Regel oder eben die 'n verändert sich'-Variante, etwas hinkucken muss man schon

zwischen 1 und n gibts nicht viele Alternativen zu log(n)

 

[Gast]

ok, ich geb auf, ich raffs einfach nicht. ist zb bei j die laufzeit n² oder n^3??? das ist doch n*(n+n) und demnach n². Komilitone saget aber gerad es wär n^3?!?

 

[SlaterB]

j hat eine Schleife, die bis a(n) läuft, also ungefähr bis n,
dieses eine a(n) zu berechnen dauert O(n)

in jedem der n Schleifendurchläufe wird einmal a(n) mit O(n) berechnet,
demnach n*n = n^2

so, das wars dann aber auch endgültig mit derart genauen Tipps

 

[Gast]

naya, das gilt ja so auch für i, jedocjh wird ja bei j in jeder schleife auch im schleifebkopf a(n) berechnet, oder geschieht das nur 1mal?

 

[SlaterB]

ok, diesen Punkt hatte ich gerade nicht bedacht,
ändert aber am Ergebnis nix, n * (2*n) ist immer noch n^2

 

[Ark]

Wenn ich Fall a richtig lese, wird da die Quadratwurzel gezogen, und zwar in entsprechend großer Zeit. --> O(sqrt(n))

Die Schleife in Fall j wird, weil a(n) die Quadratwurzel berechnet, eben sqrt(n)-mal durchlaufen. In der Schleife selbst wird dann noch mal die Wurzel gezogen (unnötigerweise, denn n ist konstant; man könnte die Wurzel auch einmal ziehen, dann würde dieser Faktor jetzt wegfallen), also wird sqrt(n)-mal die Wurzel aus n (mit O(sqrt(n))) berechnet. Das führt mich für Fall j zu O(sqrt(n) * sqrt(n)) oder eben O(n).

Ark

EDIT: Flüchtigkeitsfehler korrigiert.

PS: Ich hatte solche Berechnungen bis jetzt nur sehr selten gemacht, und ich kenne auch nicht alle Regeln (weiß aber, dass z.B. konstante Faktoren rausfallen), darum ... weiß ich nicht, ob das korrekt ist. ^^

 

[Gast]

uih, a hat laufzeit wurzel n??? is logisch und ändert einiges, dann is i und j ja nur noch n und nicht n²

 

[SlaterB]

@Ark
nicht so tiefstapeln wenn du andere korrigierst
ich sollte dann wirklich keine Tipps mehr geben

 

[Ark]

@Ark
nicht so tiefstapeln wenn du andere korrigierst

Ich habe momentan ein intellektuelles Hoch. Es wäre zu schön, wenn es anhalten würde, aber leider geht auch das vorbei.

Heißer Tipp an alle: Beschäftigt euch mal mit dem schriftlichen Radizieren (Wurzelziehen) und Logarithmieren, dann springen euch einge Sachen regelrecht ins Auge.

Ark

 

[Java Einsteiger]

Hallo!
Ich hatte ebenfalls die Aufgabe zu folgenden Methoden die Lauzeit in O-Notation zu bestimmen...

    static int a(int n){       

        int t=1, z=0;
       
        while (n>0){
            n -= t; t += 2; z++;
        }
        return z;
    }


    public static int b(int n){
       int i=0;
       int b=1;

       while(++i<n){
          b=b+2*i+1;
       }
       return b;
    }
   

    static int c(int n){

        int z=0;

        while (n>1){
            n/=2; z++;
        }
        return z;
    }


      static int d(int n){

          return a(b(n));
      }   
       

      static int e(int n){

           return b(a(n));
      }   


     static int f(int n){

       return a(c(n));
     }


     static int g(int n){

       return a(n) + c(n);
     }


      static int h(int n){

          return b(b(n));
      }
   

     static int i(int n){

        int z=0;
        int y=a(n);

        for(int i=1; i<=y; i++)

            z+=a(n);

        return z;
    }


    static int j(int n){

        int z=0;

        for(int i=1; i<=a(n); i++)

            z+=a(n);

        return z;
    }

Habe mir nun mal Gedanken gemacht und bin zu folgenden Ergebnissen gekommen:
a=O(Wurzel(n))
b=O(n)
c=O(log(n))
d=O(n)
e=O(Wurzel(n))
f=O(log(n))
g=
h=O(n^2)
i=O(n)
j=O(n)

Bei g steige ich noch nicht ganz durch....! Es wäre nicht schlecht wenn mal jemand drüber schaun kann damit ich einen Anhaltspunkt erhalte ob das ganze soweit erstmal stimmt!
Danke im Voraus!