Komplexität do while Programm

Sonnenblume123

Aktives Mitglied
Hallo,
ich hab folgendes Programm gegeben:
Code:
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
 

VfL_Freak

Top Contributor
Moin,
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) !

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
 

httpdigest

Top Contributor
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.
 

httpdigest

Top Contributor
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:
Java:
  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

Aktives Mitglied
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

Top Contributor
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

Aktives Mitglied
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?
 

httpdigest

Top Contributor
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

Aktives Mitglied
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

Top Contributor
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.
 

Neue Themen


Oben