Analysieren Sie die Median-der-Mediane Strategie, wobei die \(N\) Elemente der Folge in

Question

(1)  \( ⌊\frac { N }{ 3 }⌋ \) Gruppen mit 3 Elementen und höchstens eine Gruppe mit weniger als 3 Elementen, bzw.

(2)  \( ⌊\frac { N }{ 7 }⌋ \) Gruppen mit 7 Elementen und höchstens eine Gruppe mit weniger als 7 Elementen

aufgeteilt werden.

a. Geben Sie die Rekursionsgleichung an, die die Anzahl der Schritte abschätzt, die erforderlich ist, um das Element mit \(i\)-t kleinstem Schlüssel zu finden.
b. Zeigen Sie die lineare Laufzeit des Verfahrens für den Fall (2) und bestimmen Sie ein \(c\) in Abhängigkeit von \(a\) und das dazugehörige, minimale \(N\).

Comments

Hat jemand vielleicht einen Tipp? Brauche die Aufgabe nämlich auch. Danke im voraus.

---

Wäre auch interessiert

---

Brauchen das auch, unser Skript ist leider für die Tonne. Wir hocker hier zu dritt. Hat jemand vielleicht einen Ansatz.

---

Ich krieg das auch nicht hin. Kein Plan wie wir das machen sollen.

---

Wäre schön, wenn du es als Kommentar geschrieben hättest ;)

---

Sorry, ich war wohl gestern zu nervös^^, habe das leider nicht gemerkt. :D

Answer 1

a)

$$ \text{1) } T(n)\leq T(\lceil \frac{n}{7} \rceil)+T(\lceil \frac{5n}{7} + 8 \rceil) + a \cdot n $$

$$ \text{2) } T(n)\leq T(\lceil \frac{n}{3} \rceil)+T(\lceil \frac{2n}{3} + 4 \rceil) + a \cdot n $$

b)

$$ \text{Gesucht wird eine Konstante c, so dass } T(n) \leq c \cdot n \text{ für alle } n \geq n_{0}. $$

$$ T(n)\leq c \cdot \lceil \frac{n}{7} \rceil + c \cdot \lceil \frac{5n}{7} + 8 \rceil + a \cdot n \leq c \cdot \frac{n}{7} + c + c \cdot \frac{5n}{7} + 9c + a \cdot n = \frac{6}{7} c \cdot n + 10c + a \cdot n$$

$$ \text{c nun so wählen, dass }  \frac{6}{7} c \cdot n + 10c +a \cdot n \leq c \cdot n \text{ unter der Bedingung } c \gt 14a. $$

$$ \frac{6}{7} c \cdot n + 10c +a \cdot n \lt \frac{6}{7} c \cdot n + 10c + \frac{n \cdot c}{14} = \frac{13}{14}n \cdot c + 10c \leq c \cdot n$$

$$ \text{Daraus folgt, dass } 10 \lt \frac{n}{14} \text{ und } n \geq 140. $$

$$ \text{Die Laufzeit des Verfahrens ist also mit } c \gt 14 a \text{ für alle } n \gt 140 \text{ linear}. $$