Alg entwerfen und Laufzeit bes < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:54 Fr 08.05.2009 | | Autor: | Tobus |
| Aufgabe | Geben sie einen Algorithmus an, der das folgende Problem möglichst effizient löst und schätzen sie seine Worst-Case-Laufzeit ab.
Gegeben: ist ein Feld mit n Zahlen [mm] a_{1}...a_{n}
[/mm]
Gesucht: Zwei Indizes, so dass die Differenz [mm] a_{j}-a_{i} [/mm] maximal ist |
Zum Algorithmus:
Ich würde behaupten dass der Quicksort hier sehr effizient ist. Ich lasse sortieren, nehme den Indizes der größten und kleinsten Zahl und habe somit eine maximale Differenz
Selber entworfen hab ich folgenden:
[mm] x=a_{1}
[/mm]
[mm] y=a_{2}
[/mm]
if x<y do nul;
else x<->y (x und y vertauschen)
end if;
for i=3 to n do
if [mm] a_{i}
if [mm] a_{i}>y [/mm] do [mm] y=a_{i}; [/mm] end if;
end for;
Somit habe ich in x das kleinste, in y das größte Element.
Wie ich auf die Laufzeit komme weiß ich leider nicht genau. Ich muss doch nur die Operationen, nicht die Vergleiche Zählen oder ?
Ich komme im
1. Absatz auf 2
2. Absatz auf max. 1
3. Absatz auf max. n-2
Operationen
Meine Laufzeit ist also kleiner als (n+1)
Richtig ?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:49 Fr 08.05.2009 | | Autor: | Gilga |
Ich kann darin leider nicht Quicksort erkennen.
Sotieren ist auch nicht nötig. Einfach das kleinste und größte Element sowie deren Indizes in einem Durchlauf suchen.
Komplexität O(n)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:51 Fr 08.05.2009 | | Autor: | Tobus |
Die Sache mit dem Quicksort war nur allgemein gedacht,
meins ist natürlich kein Quicksort.
Genau nach dem kleinsten bzw größten Element suche ich ja auch in einem Durchlauf.
Würde meines, sowie die Laufzeitberechnung stimmen ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:48 Fr 08.05.2009 | | Autor: | Gilga |
Wo werden denn in deinem Algorithmus die Indizes berechnet.
Komplexität ist Feldlänge*(Vergleiche + Zuweisungen)
|
|
|
|
