Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Laufzeit berechnen
Hallo,
wie wird in der Aufgabe 1c der Klausur vom 16.02.16 berechnet,
dass T_(n/log_2(n)) = T_(floor(n/2)) = O(log_2(n)) gilt?
Hi,
Das liegt am Lemma von Brent. Wir haben einen (floor(n/2))-verteilten Algorithmus mit Anzahl der Schritten in O(log_2(n)).
Wenn wir diesen Algorithmus nun auf (floor(n/2))/(log_2(n)) Prozessoren verteilen, befinden wir uns immer noch in derselben Schrittklasse.
Siehe auch hier.