B
Brombeere
Gast
Hallo,
ich versuche gerade eine Vorlesung nachzuarbeiten und verstehe dabei folgendes Thema überhaupt nicht:
Gegeben ist ein Programmtext in Java:
Hieraus soll nun eine Laufzeit bestimmt werden.
Als Herangehensweise wird gesagt, man solle die Rekursionsformel ablesen.
Diese lautet:
vereinfachende Annahme: n = 2k
T(n) = {O(1) für n=1
2 T(n/2) + O(n) für n > 1
Das erschließst sich mir leider überhaupt nicht. Wie kommt man darauf?
ich versuche gerade eine Vorlesung nachzuarbeiten und verstehe dabei folgendes Thema überhaupt nicht:
Gegeben ist ein Programmtext in Java:
Java:
static void merge(int[] a, int left, int middle, int right) {
int[] b = new int[a.length];
for (int k = left; k <= middle; ++k) { b[k] = a[k]; }
for (int k = middle + 1; k <= right; ++k) {
b[right + middle – k + 1] = a[k];
}
int i = left;
int j = right;
for (int k = left; k <= right; ++k) {
if (b[i] < b[j]) { a[k] = b[i++]; }
else { a[k] = b[j--]; }
}
}
Hieraus soll nun eine Laufzeit bestimmt werden.
Als Herangehensweise wird gesagt, man solle die Rekursionsformel ablesen.
Diese lautet:
vereinfachende Annahme: n = 2k
T(n) = {O(1) für n=1
2 T(n/2) + O(n) für n > 1
Das erschließst sich mir leider überhaupt nicht. Wie kommt man darauf?