kostenloser Webspace werbefrei: lima-city

O-Notation im InfoLK Unterricht

lima-city → Forum → Sonstiges → Schule, Uni und Ausbildung

1. Autor dieses Themas

   garlian

   

   garlian hat kostenlosen Webspace.

   14:50, 31.5.2010

   Hallo liebe Leute,
   wir hatten vor kurzem die O-Notation zur Aufwandsbetrachtung von Algorithmen, jedoch verstehe ich da nicht so ganz, wie das im praktischen Aussieht, nehmen wir mal ein Beispiel:
   
   Kleine Java Funktion:
   

   //A1
   public void counter(int n) {
        for(int i=0;i<=n;i++) {
             System.out.println(i);
        }
   }

   
   
   Wie hoch ist denn da der Aufwand? Oder z.B. hier:
   
   

   //A2
   public void counter(int n) {
        for(int i=0;i<=n;i++) {
             System.out.println(i);
             for(int c=0;i<=n;c++) {
                  System.out.println(c);
             }
        }
   }

   
   
   Wie wäre der Aufwand hier???
   Und wie schreibe ich das ganze auf?? Freue mich auf eure Antworten, ich konnte im Internet nicht so recht das finden, was mir weiterhilft.
   
   Mit freundlichen Grüßen,
   Garlian
   

2. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

3. alphara

   

   alphara hat kostenlosen Webspace.

   23:53, 31.5.2010

   Das ist ganz einfach.
   Du gehst davon aus, System.out.println() hat den Aufwand O(1) [Ja, ich weiß, dass das ein Methodenaufruf ist und sich da je nach Methode Schleifen verbergen können. Aber in diesem Beispiel sollte die Annäherung reichen]. Im ersten Beispiel wird dieser Befehl durch die Schleife n mal aufgerufen, also hast du den Aufwand n*O(1)=O(n).
   
   Anmerkung: Da dies erst für große n von Bedeutung ist, haben ein oder zwei oder 10 Befehle mit dem Aufwand O(1) auch nur den Aufwand O(1).
   
   Im 2. Beispiel läuft die Schleife mit dem Aufwand O(c) ebenfalls n mal durch, also bekommt man einen Aufwand von n*O(c)=O(n^2). (wenn n>c, sonst O(c^2))
   
   Du musst also schauen, wo sich die Schleifen verstecken. Je mehr Schleifen man verschachtelt, je größer der Aufwand. (Man nimmt dann die größte CounterVariable und multipliziert sie sooft mit sich selbst, wie Schleifen verschachtelt sind)
   Von diesem System weicht man dann ab, wenn in verschachtelten Schleifen die Durchlaufzahlen sehr stark variieren (sich zum Beispiel immer halbieren). Dann nähert man das logarithmisch an.
   
   Betrachte das ganze als Angabe für die Geschwindigkeit einzelner Programmabschnitte. Dabei wird immer nur die oberste (=langsamste) Grenze betrachtet. (Also läuft ein Programm mit Abschnitten in O(1), O(n) und O(n^2) in der gesammten Betrachtung auch in O(n^2)). Des weiteren gilt natürlich: je höher die Potenz, um so Aufwändiger (langsamer) ist dein Programm
   
   Ich hoffe, dass das verständlich ist. Andernfalls gibts es noch sehr gute Wikipediaartikel dazu.
   
   PS: Das gilt natürlich nur für die "groß-O"-Notation, mit welcher man eine obere Grenze beschreibt (und dabei kann man auch jede größere wählen. Programme, die in O(n) laufen, liegen demnach auch in O(n^2) aber nicht umgekehrt). Man kann mit Landausymbolik noch jede Menge andere Grenzen beschreiben ("klein-o"=kleinste obere Schranke,"klein-omega"=größte untere Schranke,"groß-Omega"=eine untere Schranke ..........)
   
   Beitrag zuletzt geändert: 1.6.2010 0:18:10 von alphara

4. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?