Laufzeitanalyse < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:36 Sa 24.11.2007 | | Autor: | tommy987 |
| Aufgabe | | Bestimmen Sie O(Heapsort) und Omega(Heapsort)! |
Hallo!
Die Frage hab ich selber grad erfunden, aber mir gehts darum, wie ich allgemein die Laufzeiten, bzw. Grenzen verschiedener Algorithmen herleiten und bestimmen kann?
lg Thomas
|
|
| |
|
Du schaust dir den Algorithmus z.B. im Pseudocode an und überlegst dir, welche Operation wielange benötigt und wie oft diese durchgeführt wird.
Bei Heapsort wären das also die Operationen "baueHalde()" und "reheap()", die du betrachten musst. Wie oft werden diese Operationen benötigt?
Dementsprechend kannst du dann O bestimmen, indem du mit den Eingabewerten (z.B. n Eingabewerte => Heapsort ist beschränkt durch O(n*log(n)) das Ganze abschätzt :)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:53 So 25.11.2007 | | Autor: | tommy987 |
Hallo!
Wir haben es so gehandhabt, dass wir zuerst geschaut haben wie du eben gesagt hast, die Zeilen zu analysieren und dann die Laufzeit zu ermittlen. Wir haben es dann immer für einen Fall gemacht, z.B.: T(n) = T(n-1) + O(1) und dann iterativ eingesetzt. So sind wir zum O(Algo) gekommen. Doch wie fasse ich die Zeilen dann zusammen und werte sie dann aus?? Hast du vielleicht irgend einen kleine BspAlgo., wo du mir die Schritte zeigen kannst bis zum Ende?
Danke schon mal!
lg Tommy
|
|
|
| |
|
Ja also das ist es doch eigentlich schon. Du schaust einfach ob und wieoft welche Befehle durchgeführt werden und wielange du dafür brauchst.
Wenn du z.B. wählst:
1. Setze x = 0
2. Setze y = 10*n
3. while (x < y)
4. setze x = x+1;
5. endwhile;
(n sei eine Eingabe)
Dann schaust du dir an: Wieoft wird 1.) durchgeführt? => 1x. Wielange brauche ich dafür? O(1), also Konstantzeit.
2. Genauso
Nun kommt der Anweisungsblock von 3.-5. Dieser Block wird y = 10*n mal durchgeführt. Die Anweisung in 4. kann ich wieder in Konstantzeit durchführen, d.h. der Block braucht O(10*n) = O(n). Der ganze Algo oben hat also Laufzeit O(n).
Wenn du Heapsort postest, können wir es natürlich daran auch mal gemeinsam durchführen. :)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:27 So 25.11.2007 | | Autor: | tommy987 |
Prinzipiell hast du in deinem Bsp. schon die obere Schranke gesetzt, die Laufzeit wäre aber in diesem Fall eine Summe der einzelnen Zeilen, bzw. wenn etwas iterativ aufgerufen wird, dann halt z.B.: T(n) = [mm] T(\bruch{n}{2}) [/mm] + O(1) + ..., oder?
lg Thomas
|
|
|
| |
|
Ja eigentlich ist es genau das. Die Überlegung ist halt, dass die Schleife n mal durchlaufen werden muss und bei jedem Durchlauf O(1) Kosten verursacht.
D.h. wir haben n*O(1) und das ist genau O(n).
Dein Beispiel mittels T(n/2) ist soweit korrekt, das machst du z.B. bei Divide-Et-Impera (auch: "Teile und Herrsche" oder "Divide And Conquer") Algorithmen wie z.B. Quicksort so!
|
|
|
|
