Notice: Undefined variable: useragent in /srv/users/matheretter/apps/mathelounge/public/qa-theme/lounge/qa-theme.php on line 2241
0 Daumen
1,4k Aufrufe

(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\).

von

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

1 Antwort

0 Daumen

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}. $$

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community