Laufzeitkomplexität von Algori < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Elementen und einen Algorithmus, der einzelne Elemente bearbeitet. Das kostet n2 +
7 log n Operationen pro Element. Alle Elemente mussen bearbeitet werden.
a) Wie lange dauert das (mit und ohne -Notation)?
b) Die Bearbeitung zweier Elemente ist unabhangig voneinander, man kann sie also
parallelisieren. Dazu stehen 8 Kerne zur Verfugung. Wie wirkt sich dies auf die
Gesamtlaufzeit aus (mit und ohne -Notation)?
c) Alternativ kannst du ein Preprocessing verwenden, welches in 3n log n+4n7 lauft
und danach die Bearbeitungszeit pro Element auf log n reduziert, allerdings ist die
Bearbeitung der Elemente dann nicht mehr parallelisierbar. Wie wirkt sich das auf
die Gesamtlaufzeit aus (mit und ohne -Notation)?
d) Fur welche Moglichkeit (ursprunglicher Algorithmus, b), oder c)) entscheidest du
dich, um die Leistungsfahigkeit des Programms fur groe Inputmengen zu maximieren?
Begrunde deine Wahl. |
Hallo zusammen!
Könnte jemand mir mit einer Aufgabe helfen? Ich weiß bloss nicht wie ich anfangen soll(( Danke.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Hallo ardis,
es scheinen einzelne Zeichen in der Aufgabenstellung verloren gegangen zu sein (Oder zeigt es die nur bei mir nicht an? Wen dem so ist, bitte entsprechende Rückmeldung). So ist die Aufgabe nur schwer für mich rekonstruierbar.
Ich vermute, ein Algorithmus durchläuft eine Liste von Elementen mit einer bestimmten Laufzeit pro Element, und du sollst nun Laufzeiten absolut und in Groß-O-Notation angeben, d.h. konstante und lineare Laufzeitfaktoren vernachlässigt.
Wo genau liegt dein Verständnisproblem?
Verstehst du nicht, wie sich die Laufzeit überhaupt berechnet?
Verstehst du die Groß-O-Notation nicht?
Verstehst du nicht, wie sich die einzelnen, in den Aufgabenteile vorgeschlagenen Optimierungen auf die Laufzeit auswirken?
Gruß,
Sandro
|
|
|
| |
|
hallo sandroid,
danke für deine Antwort!
Ich habe leider einen Fehler in der Aufgabenstellung begangen. Es geht um die ϴ-Notation, nicht aber um Ο-Notation. Ich verstehe ganz gut wie man die Laufzeit mit O,ϴ,Ω Notation berechnet.
In erster Linie verstehe ich nicht , wie man ohne Notationen berechnet?? Wie soll ich anfangen? Soll ich zuesrt die Laufzeit mit dieser Funktion (n2 + 7 log n) und nachher dieser Funktion mit ϴ-Notation, ansschließend muss die Ergebnisse von denen verglichen werden?? Zweitens, in b) -soweit ich verstanden habe-
soll meine Funkion (n2 + 7 log n) durch 8 dividieren , denn ich nun 8 Kerne habe, das heßt jeder Kern bearbeite genau ein Element? und es wird hier auch ohne Notation und mit Notation berechnet ?
Das verstehe auch nicht "Verstehst du nicht, wie sich die einzelnen, in den Aufgabenteile vorgeschlagenen Optimierungen auf die Laufzeit auswirken? "
Hättest Du welche Ideen um mir dabei zu helfen?. Ein kleines Beispiel wäre ausreichend
VG
Toni
|
|
|
| |
|
Hallo Toni,
so viel zunächst zur Theorie: Die Laufzeit ist die Anzahl elementarer Rechenoperationen, also Additionen, Subtraktionen etc... . Diese Laufzeit hängt meistens von einer Variable $n$ ab, i.d.R. von der Anzahl der Elemente in einer Liste, die verarbeitet werden, auch genannt "Eingabegröße".
Die Formel für die Laufzeit in Abhängigkeit von $n$ benötigst du. Mithilfe von dieser kannst du dann die [mm] $\Theta$-, $\Omega$-, [/mm] $O$-Notation herleiten, nämlich, indem du konstante lineare Faktoren weg lässt.
Zu deiner konkreten Aufgabe:
Ich habe leider immer noch nicht die ersten Worte des Aufgabentextes. Wie fängt der erste Satz an? Wie viele Elemente müssen verarbeitet werden? $n$ Elemente? Und pro (!) Element braucht der Algorithmus [mm] $n^2 [/mm] + 7*log(n)$ Operationen, ja?
Dann hättest du ja die Laufzeit pro Element. Multipliziert mit der Anzahl der Elemente gibt das dann die Gesamtlaufzeit. Versuche nun, die Formel für die Laufzeit aufzustellen und zusätzlich in [mm] $\Theta$-Notation [/mm] anzugeben. Dann sehen wir weiter.
Mit 8 Kernen teilt sich die Laufzeit durch 8, genau (Auch wenn das in der Realität in der Tat unrealistisch ist).
Gutes Gelingen,
Sandro
|
|
|
|
