Aus ProgrammingWiki
< AuK < Teile und Herrsche 1 SS11 Aufgaben
Archivierte Version vom 2011-04-28T11:37:00+00:00. Aktuelle Version

Übungsaufgaben

1. Zu Beginn unserer Vorlesung wiesen wir die Effizienz von Teile-und-Herrsche-Algorithmen mit der Meister-Methode nach. Aufgabe ist es nun, die Effizienz iterativ nachzuweisen. Folgende Aufwandsbeziehungen gelten:

T_C \left( n \right) =\begin{cases} T_A \left( n \right), & \text{wenn } \ n \ \leq \ n_0, \\ 3 \cdot T_C \left( \frac{n}{2}\right), & \text{sonst } \end{cases}


2.


3.