O-Notation

[ocsme]

Hallo,

(hab den Titel leider vergessen zu ändern!)

ich hab eine Aufgabe in Pseudocode gegeben und soll dazu die O-Notation bestimmen. Doch leider stehe ich total auf dem Schlauch.

Hier erst einmal die Aufgabe:

Gegeben sei der folgende Algorithmus in Pseudocode-Notation.
Bemerkung: a[] ist ein Array [0..n-1] gefüllt mit n Zahlen aus der Menge {0,1}

T = 0
For i = 0 to (n-1) {
   For j = n downto (n+i) {
   k = j
       while ( k >= 0){
          k= k -1
          T = (T + a[k]) mod 2 // „mod“ gibt den ganzzahligen Divisionsrest zurück
      }
   }
}
GibAus(T) // zu interpretierendes Ergebnis

a) Schätzen Sie anhand der O-Notation den Laufzeitaufwand ab hinsichtlich der inneren Additi-
on von T.
b) Was können Sie anhand des Ergebnisses/der Ausgabe über den Inhalt des Arrays aussagen?
c) Welche Komplexität (in O-Notation) hat das Problem (Aussage aus b) eigentlich?

Leider verstehe ich schon a) nicht.

Meine Überlegung bei dieser Aufgabe war folgende:
For i = 0 to (n-1) { läuft n-1 mal
For j = n downto (n+i) { wäre n = 0 so ergibt sich hier das die Schleife i mal läuft
nun kämm das Problem denn dann wäre:
while ( k >= 0) mehr oder weniger 0 bzw. ist ja abhängig von j somit j mal somit i mal!

Meine Abschätzung geht dann in O(n³) das stimmt aber nicht da ich es in Java getextet habe und andere Ergebnisse raus kommen 🙁 bei n = 6 kommen 182 Schleifen Durchläufe raus und keine 216. Da es nur eine Abschätzung ist denke ich liege ich trotzdem daneben 🙁

Kann mir das vielleicht irgendwie jemand erklären?

LG

 

[httpdigest]

For j = n downto (n+i) {

Bist du sicher, dass du die Aufgabe richtig abgeschrieben hast? "downto" impliziert, dass hier "herab" gezählt wird. Das geht aber nicht, wenn die Anfangszahl `j = n` kleiner ist als die Zahl `n+i`, zu der herabgezählt werden soll (mit i >= 0).

 

[ocsme]

For j = n downto (n+i) {

Bist du sicher, dass du die Aufgabe richtig abgeschrieben hast? "downto" impliziert, dass hier "herab" gezählt wird. Das geht aber nicht, wenn die Anfangszahl `j = n` kleiner ist als die Zahl `n+i`, zu der herabgezählt werden soll (mit i >= 0).

Die Aufgabe ist komplett Kopiert.
Stimmt das ist mir nicht mal aufgefallen 🙁
Wenn ich j = n = 0 setzen würde hätte man eine Endlosschleife die immer inkrementiert z. B. 🙁 so ein Misst!

Das steht aber genau so in der Aufgabe!


Ich verstehe das Thema mit der Komplexität eh nicht so richtig! Wie bekommt man den in so etwas mehr Übung?

 

[httpdigest]

Also ich hätte bei dieser Aufgabe, bzw. genauer gesagt bei dem Pseudo-Code, nur Fragezeichen im Kopf:

1. Das besagte `for j = n downto (n+i)`. Wenn das wirklich wörtlich gemeint ist, würde es in Java übersetzt so aussehen: `for (int j = n; j >= n+i; j--)`. Diese Schleife würde also nur genau einmal laufen, wenn i == 0 ist. Das kann entweder ein fieser Trick sein, oder ein Fehler in der Aufgabenstellung. Keine Ahnung.

2. In der inneren Schleife wird `k` im letzten Durchlauf der Schleife immer `-1` sein und es wird auf das Array `a` mit Index `-1` zugegriffen. Was soll das denn? Was genau wäre in dieser Pseudosprache die operationale Semantik einer Arrayindexierung mit negativem Index? Es gibt ja Sprachen, in denen es bedeutet "Fange von hinten im Array an". Ist das hier auch so? Keine Ahnung. Vielleicht ist es auch nur ein Fehler in der Aufgabenstellung.

Diese Fehler (oder vielleicht absichtlich so gestellte Aufgabe) machen es jetzt umso schwerer, Aufgabe b) zu beantworten. Was da genau als Ergebnis rauskommt, hängt davon ab, ob Punkt 1 oben so wörtlich zu nehmen ist und, dass Punkt 2 geklärt bzw. der Fehler in der Aufgabe behoben wird.

Wenn der Fehler aus Punkt 2 behoben ist, aber Punkt 1 so wörtlich gemeint ist, hat die ganze Sache eine Komplexität von `O(n)`, wenn man nur die Laufzeit der inneren Addition betrachtet (wie in Aufgabe a gefordert).
Das liegt daran, dass (wie gesagt) die zweite Schleife nur genau einmal läuft, wenn i (aus der äußersten Schleife) = 0 ist. Das eigentliche Addieren passiert dann nur in der inneren while-Schleife.

Wenn Punkt 1 so nicht gemeint war, ist die Frage: Wie war es denn gemeint? `for j = n downto (n-i)`?
Das kann man jetzt annehmen, und so erstmal weitermachen. Aber sicher ist das nicht.

Was mich zum letzten Punkt bringt: Wie hast du diesen fehlerhaften Pseudocode denn eigentlich in Java übersetzt, um die eigentlichen Additionsoperationen der inneren while-Schleife zu zählen?

 

[mihe7]

Gehen wir mal von

public class Test {
    public static void main(String[] args) {
        int t = 0;
        int m = 0;
        int n = args.length;
        for (int i = 0; i < n; i++) {
            for (int j = n; j >= n-i; j--) {
                int k = j;
                while (k > 0) {
                    m++;
                    k--;
                    t = (t + Integer.parseInt(args[k])) % 2;
                }
            }
        }
        System.out.println(t);
        System.out.println(m);
    }
}

aus. Die Frage ist: was ist m? Das kann man ausrechnen (wenn man will 🙂)

Im Schleifenkörper der while-Schleife wird m um 1 erhöht. Die while-Schleife wiederholt den Spaß für k=j bis runter auf 1 oder umgekehrt von k=1 bis j. Bis dahin haben wir also einfach m = j.

Die innere for-Schleife wird nun für j = n bis runter auf n-i oder eben umgekehrt von j=n-i bis n wiederholt, d. h.

m = (n-i)+(n-i+1)+(n-i+2)+...+(n-i+i)
  = (n-i)+0 + (n-i)+1 + (n-i)+2 + ... + (n-i) +i
  = (i+1)*(n-i) + 0+1+2+...+i  
  = (i+1)*(n-i) + i*(i+1)/2     
  = (i+1)*n - (i+1)*i + i*(i+1)/2
  = (i+1)*n - 2(i+1)*i/2 + i*(i+1)/2
  = (i+1)*n - (i+1)*i/2

Die äußere for-Schleife wird von 0 bis n-1 wiederholt, daraus ergibt sich

Das führt zunächst zu

und über

am Ende zu

D. h. m(n) = (2n^3 + 3n^2 + n)/6

Damit ist klar, dass m(n) nicht wesentlich schneller als n^3 wächst, was nichts anderes bedeutet, als dass m ein Element von O(n^3) ist. Das lässt sich natürlich auch beweisen:

Behauptung: für alle n >= 1 gilt m(n) <= n^3

m(n) <= n^3
<=> 2n^3 + 3n^2 + n <= 6n^3
<=> 3n^2 + n <= 4n^3
<=> 3n+1 <= 4n <= 4n^2

 

[ocsme]

Erst einmal Danke an euch beide 🙂
Das wäre nun die Erklärung für a oder?

Schätzen Sie anhand der O-Notation den Laufzeitaufwand ab hinsichtlich der inneren Additi- on von T.

O(n³)

Das ganze war bei mir leider nicht richtig gerechnet 🙁
Wie übt man so etwas? Kann mir dabei jemand einen Tipp geben?

Und was ist mit b) und c)?

LG

 

[mihe7]

Das ganze war bei mir leider nicht richtig gerechnet

Das sollte nur als Beispiel gedacht sein. Normalerweise rechnet man das auch nicht, sondern überschlägt es, wie Du es getan hast. Nur manchmal sind die Zusammenhänge nicht ganz offensichtlich, da lohnt es sich dann, genauer hinzuschauen.

Zu b) und c) frag erst mal nach, ob der Code wirklich wie in der Aufgabe gestellt genommen werden soll. Dann wird die Sache recht einfach 🙂

Sonst wird es kompliziert (oder ich sehe den Trick nicht).

 

[ocsme]

Das zu überschlagen geht ja noch doch leider habe ich mich verrechnet und das ärgert mich nun auch wieder!!! 🙁

Ja die Aufgabe ist so korrekt doch leider verstehe ich nicht wirklich was mit b) und c) gemeint ist? Ist da ein Trick hinter?

LG

 

[mihe7]

Ja die Aufgabe ist so korrekt doch leider verstehe ich nicht wirklich was mit b) und c) gemeint ist?

Wenn die Aufgabe so bearbeitet werden soll, siehe den Kommentar von @httpdigest

a) Laufzeit: O(n)
b) nichts, weil a[-1] nicht existiert (außer, damit soll das letzte Element gemeint sein, s. @httpdigest)
c) da in b) kein Problem gelöst wird, kann auch keine Laufzeit angegeben werden.

 

[ocsme]

:O b) und c) verstehe ich ja 🙂
Doch wieso ist die Laufzeit nun bei der Addition bei 3 Schleifen die wie oben Berechnet wurden O(n)? Läuft die Addition nicht O(n³)? jetzt bin ich ganz raus. Das mit dem a[-1] ist mir nicht mal aufgefallen da dort ja >= 0 steht und nicht > 0 😀

LG

 

[httpdigest]

Doch wieso ist die Laufzeit nun bei der Addition bei 3 Schleifen die wie oben Berechnet wurden O(n)? Läuft die Addition nicht O(n³)?

Wenn der Fehler aus Punkt 2 behoben ist, aber Punkt 1 so wörtlich gemeint ist, hat die ganze Sache eine Komplexität von `O(n)`, wenn man nur die Laufzeit der inneren Addition betrachtet (wie in Aufgabe a gefordert).
Das liegt daran, dass (wie gesagt) die zweite Schleife nur genau einmal läuft, wenn i (aus der äußersten Schleife) = 0 ist. Das eigentliche Addieren passiert dann nur in der inneren while-Schleife.

 

[ocsme]

Gestern hatte ich schon beim lesen Problem uff...!!!
Danke nochmals 🙂

LG