Hallo,
ich hab zwei Java Programme gegeben und soll sagen in welcher O Klasse diese liegen.
Programm 1:
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:
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
ich hab zwei Java Programme gegeben und soll sagen in welcher O Klasse diese liegen.
Programm 1:
Code:
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:
Code:
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