# O-Notation



## ocsme (16. Aug 2019)

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 (16. Aug 2019)

```
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 (16. Aug 2019)

httpdigest hat gesagt.:


> ```
> 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 (16. Aug 2019)

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 (17. Aug 2019)

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 (17. Aug 2019)

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


ocsme hat gesagt.:


> 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 (17. Aug 2019)

ocsme hat gesagt.:


> 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 (17. Aug 2019)

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 (17. Aug 2019)

ocsme hat gesagt.:


> 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 (17. Aug 2019)

: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 (17. Aug 2019)

ocsme hat gesagt.:


> 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³)?





httpdigest hat gesagt.:


> 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 (18. Aug 2019)

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

LG


----------

