Komplexität angeben

[Sonnenblume123]

Hallo,

ich hab zwei Java Programme gegeben und soll sagen in welcher O Klasse diese liegen.
Programm 1:

public int function1(int n) {
        if (n == 0) {
            return 0;
        }
        if (n % 2 == 0) {
            return function1(n / 2);
        } else {
            return 1 - function1((n - 1) / 2);
        }
    }

Hier habe ich mir folgendes überlegt:
Wenn n gerade ist, wird die zweite if-Verzweigung ausgeführt, weil n gerade ist, wird nur diese if Verzweigung aufgeführt bis n = 0 gilt, daher wird n immer halbiert. Daher hier O(log (n)).
Wenn n ungerade ist, wird die else Verzweigung ausgeführt, weil n-1 gemacht wird, wird n dadurch gerade und daher immer halbiert wie im Fall oben.
Daher würde ich sagen, dass die function1 in O(log(n)) liegt.

Programm 2:

public int function2(int n) {
        if (n == 0) {
            return 0;
        }
        int i = 1;
        int j = n;
        while (i < j) {
            i = i + 1;
            j = j - 1;
        }
        return function2(i - 1) + 1;
    }

Hier hab ich mir überlegt, dass die while Schleife immer bis n/2 ausgeführt wird und die funktion2 auch immer n halbiert, dabei dacht ich durch das i-1+1, dass die Funktion einfach i mal aufgerufen wird und wegen der while Schleife immer log mal. Also ergibt sich O(n log (n)).
Würdet ihr mir da zustimmen?🙂
Vielen Dank im Voraus🙂

 

[httpdigest]

Bei deiner Analyse der ersten Funktion gebe ich dir Recht. Es ist: O(log(n)).
Wenn wir für die Analyse der zweiten Funktion auch annehmen, dass eine Schleifeniteration ebenfalls eine Operation darstellt, die die asymptotische Laufzeit der Funktion beeinflussen; also wenn wir sagen: Bestünde die ganze Funktion nur aus der Schleife, wäre die asymptotische Laufzeit O(n), dann können wir folgendes festhalten:
1. Wie du schon richtig gesagt hast, wird die while-Schleife immer `n/2` Mal pro Funktionsaufruf ausgeführt
2. Und wie du auch richtig sagst, wird dadurch effektiv das `n` für den nächsten rekursiven Aufruf halbiert. `i` entspricht also asymptotisch immer `n/2`, weil ja die while-Schleife sowohl `i` hochzählt als auch `j` runterzählt. Somit treffen sich `i` und `j` "in der Mitte" und `i` ist danach effektiv `n/2`.
3. Das heißt, die asymptotische Laufzeit der Funktion für ein gegebenes `n` ist eher die Summe: `n/2+n/4+n/8+n/16...`, die für n->+inf den Grenzwert `n` hat. Somit ist die korrekte asymptotische Laufzeit dieser zweiten Funktion: `O(n)`
Empirisch kannst du das auch nachvollziehen, indem du einfach einen Zähler inkrementierst für jeden Aufruf der Funktion und jede Iteration der Schleife.