Hallo, hier sind 2 Aufgaben:
1. Geben Sie eine Rekursionsformel für die Laufzeit des Aufrufs
strangeSum(a, 0, n) mit n = a.length = 3^k an. Eine explizite Formel ist nicht gefordert.
Lösung:
................cn, n < 100
T(n) ≤ {
................2T(n/3) + cn, sonst
2. In der Vorlesung hatten wir InsertionSort mit Hilfe verschachtelter Schleifen in Java implementiert. Alternativ dazu lässt sich der Algorithmus wie folgt als Rekursion auffassen: Das Sortieren eines Arrayabschnitts a[0] ... a[n-1] wird zurückgeführt auf das Sortieren des Arrayabschnitts a[0] ... a[n-2], gefolgt vom Einfügen des Elements a[n-1] in dieses sortierte Teilfeld. Geben Sie eine Rekursionsformel für die Laufzeit dieses Algorithmus an (die explizite Formel muss nicht hergeleitet werden).
Lösung:
................O(1), n = 1
T(n) ≤ {
................T(n - 1) + O(n), n > 1
Liege ich denn richtig mit den Lösungen?
1. Geben Sie eine Rekursionsformel für die Laufzeit des Aufrufs
strangeSum(a, 0, n) mit n = a.length = 3^k an. Eine explizite Formel ist nicht gefordert.
Code:
static int strangeSum(int[] a, int left, int right) {
int sum = 0;
if (right - left < 100) {
for (int i = left; i < right; ++i) {
sum += a[i];
}
}else {
int third = (right - left) / 3;
for (int i = left + third; i < left + 2 * third; ++i) {
sum += a[i];
}
sum += strangeSum(a, left, left + third);
sum += strangeSum(a, left + 2 * third, right);
}
return sum;
}Lösung:
................cn, n < 100
T(n) ≤ {
................2T(n/3) + cn, sonst
2. In der Vorlesung hatten wir InsertionSort mit Hilfe verschachtelter Schleifen in Java implementiert. Alternativ dazu lässt sich der Algorithmus wie folgt als Rekursion auffassen: Das Sortieren eines Arrayabschnitts a[0] ... a[n-1] wird zurückgeführt auf das Sortieren des Arrayabschnitts a[0] ... a[n-2], gefolgt vom Einfügen des Elements a[n-1] in dieses sortierte Teilfeld. Geben Sie eine Rekursionsformel für die Laufzeit dieses Algorithmus an (die explizite Formel muss nicht hergeleitet werden).
Lösung:
................O(1), n = 1
T(n) ≤ {
................T(n - 1) + O(n), n > 1
Liege ich denn richtig mit den Lösungen?
