Hab gerade diese frage in einem prüfungsprotokoll gelesen und gerate gerade in verweiflung… was bedeutet das bei optimalen parallel algortihmen?

wie lange braucht man eurer meinung, um den f3/4 stoff einigermaßen gut drauf zu haben?

Hab gerade diese frage in einem prüfungsprotokoll gelesen und gerate gerade in verweiflung… was bedeutet das bei optimalen parallel algortihmen?

Das ist die Zeitkomplexität des besten sequentiellen Algorithmus für ein Problem.
Ein paralleler Alg. heißt optimal, wenn seine Operationenkomplexität asymptotisch gleich der besten sequentiellen Zeitkomplexität ist. (siehe auch Skript Seite 166)
Das heisst, wenn man die Laufzeit aller Prozessoren einzeln zusammennimmt, der Parallelalgorithmus trotzdem nicht länger braucht als die beste Lösung auf einem Prozessor.
(So habe ich das jedenfalls verstanden [img]http://www.fb18.de/gfx/23.gif[/img])