# Komplexität do while Programm



## Sonnenblume123 (15. Jun 2018)

Hallo,
ich hab folgendes Programm gegeben:

```
public static void main(String[] args) {
    int [] A = {0,0,0,0,0};
    int n = A.length;
    int i;
    do {
        i=1;
        while (A[i]==1) {
            A[i]=0;
            i=i+1;
            }
        A[i]=1;
        } while (i<n);
        }
```

Wobei A eigentlich ein Array mit n Einträgen sein soll, wobei es überall auf 0 gesetzt ist. Jetzt soll ich die Komplexität dieses Programms beweisen und es ist in O(2^n). Nur bevor ich überhaupt es beweisen soll, hab ich noch Verständnisprobleme mit dem Code. Die do Bedingung wird genau einmal ausgeführt und A(1) wird auf 1 gesetzt und dann beginnt die while Schleife, wo aber i irgendwie ja nie verändert wird. Also terminiert doch das Programm eigentlich nicht.

Könnte mir deshalb einer von euch mir vielleicht erklären, wo mein Denkfehler ist?
Vielen Dank im Voraus


----------



## httpdigest (15. Jun 2018)

Sonnenblume123 hat gesagt.:


> [...]und dann beginnt die while Schleife, wo aber i irgendwie ja nie verändert wird.


Guck nochmal ganz ganz genau hin: `i=i+1;`


----------



## VfL_Freak (15. Jun 2018)

Moin,


Sonnenblume123 hat gesagt.:


> Die do Bedingung wird genau einmal ausgeführt


_*GENAU einmal*_ ist falsch!
Mindestens einmal, da hier die Bedingung NACH den Aktionen kommt - und dann solange, bis die Bedingung erfüllt ist (also solange "i < n" gilt) !



Sonnenblume123 hat gesagt.:


> Also terminiert doch das Programm eigentlich nicht.


Oh, es "terminiert" schon ... allerdings so:


> Exception in thread "AWT-EventQueue-0" java.lang.ArrayIndexOutOfBoundsException: 5


und zwar in dieser Zeile: *while (A==1)*_

VG Klaus_


----------



## Sonnenblume123 (15. Jun 2018)

Ach die do Bedingung wird solange ausgeführt, so lange i<n gilt?


----------



## VfL_Freak (15. Jun 2018)

Sonnenblume123 hat gesagt.:


> Aber die do Bedingung wird doch nur einmal ausgeführt


Nein, siehe #3 !!


----------



## Sonnenblume123 (15. Jun 2018)

Entschuldigung, hab gerade abgeschickt, als du den Beitrag geschrieben hast 
Vielen Dank hab das Programm jetzt verstanden!


----------



## VfL_Freak (15. Jun 2018)

Sonnenblume123 hat gesagt.:


> Entschuldigung, hab gerade abgeschickt, als du den Beitrag geschrieben hast


kein Problem, hatte ich mir gedacht!
Wollte nur drauf hin weisen, damit Du es nicht überliest !1

VG Klaus


----------



## Sonnenblume123 (15. Jun 2018)

Ist dann die Laufzeit O(2^n), da die untere while Schleife n Mal ausgeführt wird und wir auf jeden Index immer zwei Mal zugreifen?


----------



## httpdigest (15. Jun 2018)

Bist du sicher, dass du das Programm richtig "abgeschrieben" hast? So wie es aktuell da steht, enthält es so unglaublich viele Bugs, dass es eigentlich gar nicht möglich ist, das Programm auszuführen, ohne eine Exception zu generieren.


----------



## Sonnenblume123 (15. Jun 2018)

Stimmt, hab vorhin vergessen zu editieren, dass n = A.length-1 ist.
Danke für den Hinweis!


----------



## httpdigest (15. Jun 2018)

Da fehlt noch mehr. Schau dir mal die innere Schleife genauer an. Hier fehlt auch noch eine Bedingung, die dafür sorgt, nicht in eine ArrayIndexOutOfBoundsException zu kommen. Meiner Meinung nach sieht das korrekt Programm so aus:

```
public static void main(String[] args) {
    int[] A = { 0, 0, 0, 0, 0 };
    int n = A.length - 1;
    int i;
    do {
      i = 0;
      while (A[i] == 1 && i < n) {
        A[i] = 0;
        i = i + 1;
      }
      A[i] = 1;
      System.out.println(Arrays.toString(A));
    } while (i < n);
  }
```
Ich habe mal ein System.out.println() eingefügt, was dir erlaubt, zu sehen, was das Programm eigentlich tun soll.


----------



## Sonnenblume123 (15. Jun 2018)

Vielen Dank! Hab das vorhin beim Aufgabensteller angemerkt und er hat sie daraufhin korrigiert 
Warum ist er trotzdem in O(2^n)?
die untere while Schleife ist in O(n) und wegen dem 0 oder 1 ist es 2^n? Passt die Begründung?


----------



## httpdigest (15. Jun 2018)

Nein, so einfach ist das nicht. Für einen wirklichen Beweis muss man erstmal verstehen, was der Algorithmus eigentlich macht. Die Abbruchbedingung i >= n ist klar. Irgendwann muss mal durch die innere Schleife i soweit inkrementiert werden, bis i == n. Aber wann passiert das genau? Die innere Schleife zählt ja nur i solange hoch wie die gelesenen Arrayelement in A beginnend vom Anfang des Arrays 1 sind. Und auf 1 gesetzt wird ein Arrayelement nur durch die Zuweisung in der äußeren Schleife unten.
Durch die innere Schleife wird außerdem i immer auf das Arrayelement gesetzt, das nach allen zusammenhängenden Einsen (Beginnend von Index 0) an folgt.
Das heißt, bei A={1, 0, 0} wird die innere Schleife 1 Mal durchlaufen und i wird 1 sein. Bei A={0, 1, 0} wird sie 0 Mal durchlaufen und i ist 0. Bei A={0, 0, 1} ebenfalls 0 Mal und i ist 0, und bei A={1, 1, 0} 2 Mal und i ist 2.
Ich denke, hier ist ein Induktionsbeweis möglich.
Du musst erstmal zeigen, dass deine Induktionsbehauptung (etwa für die Fälle n=1 und n=2) wahr ist. Also einfach per Aufzeigen der tatsächlichen Algorithmusschritte zeigen, dass sowohl f(1) als auch f(2) in O(2^n) sind, wobei f(n) die Anzahl der Berechnungsschritte für einen Input der Länge n ist.
Dann musst du zeigen, dass sich die Anzahl der Schritte insgesamt verdoppelt, wenn sich n um 1 erhöht. Also f(n+1) = 2*f(n).


----------



## Sonnenblume123 (17. Jun 2018)

Kann es sein, dass der Induktionsanfang n=2 sein muss, weil wenn man f(n) = 2*f(n-1) zeigen will, steht sonst f(1) = 2*f(0) dar und f(0) ist ja nicht bekannt oder irre ich mich?


----------



## Sonnenblume123 (17. Jun 2018)

Und irgendwie klappt mein Induktionsanfang nicht, weil f(2) = 4, aber 2*f(1) = 2


----------



## httpdigest (17. Jun 2018)

Also, wenn `n = A.length - 1` (wie von dir gesagt), komme ich auf:
f(0) = 1
f(1) = 3
f(2) = 7
f(3) = 15
f(4) = 31
Also:
f(n+1) = 2*f(n) + 1   (das +1 kannst du natürlich ignorieren/vernachlässigen für die Komplexitätsabschätzung)
Dabei zähle ich jede Iteration der inneren sowie der äußeren Schleife als eine Operation.


----------



## Sonnenblume123 (17. Jun 2018)

Hab gerade nochmal auf die Aufgabe geschaut und der Aufgabensteller hat sie folgendermaßen verändert:
Arrays beginnen nicht mehr ab Index 0, sondern 1 und hören bei Index n auf.
Jetzt wird die Induktion wieder nicht möglich, weil
f(0) existiert ja jetzt nicht


----------



## httpdigest (17. Jun 2018)

Es ist doch vollkommen egal, von wo man Arrayindizes anfängt zu zählen. Meinetwegen können in der fiktiven Programmiersprache deines Aufgabenstellers Arrayindizes auch bei 526 anfangen. Das ist egal. Das `n` in f(n) ist ja nicht der Arrayindex sondern die _Anzahl_ der Arrayelemente.


----------

