Hallo,
es gibt doch bei Algorithmen best case, worst case und average case Laufzeiten. Dann gibt es noch die amortisierten Kosten. Das habe ich irgendwie gar nicht verstanden. Was ist das und wozu braucht man das bzw. wie berechnet man das ?
Grüße,
Tris
Algorithmus 2: ich sortiere zunächst alle Einträge
Kosten ca. 200 * log (200) = ca. 1600 (Quick Sort)
Dann suche ich mit Binärer Suche.
log (200) aufgerundet 8 (256)
Nach fünfzig mal Suchen: (sogar Worst Case Fall, Average Case liegt aber nicht viel darunter, Best Case auch hier 1)
1600 + 50 * 8 = 2000
Jetzt kann man sich ausrechnen ab wann sich der 2. te Algorithmus sich im Mittel lohnt (die Sortierung sich armortisiert)
1600 + 8 * x = 100 * x
92 * x = 1600
x = 17,34
d.h. nach 18 Versuchen haben sich die Kosten der Sortierung mehr als armortisiert.
Wenn wir nur einmal Suchen, lohnt sich die Sortierung gegenüber dem ersten Algorithmus nicht.
Hoffe das Beispiel hilft.
Gruss Peter
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
danke für das Beispiel.
Was ich aber dennoch nicht verstehe ist, warum nach ca. 18 Versuchen sich der 2. Algorithmus lohnt. Ich meine er kostet doch ohnehin weniger als der erste, oder ?
Also der erste kostet bei 50 Versuchen 5000, der zweite bei 50 Versuchen 2000.
Grüße,
Tris
Hi Tris,
weil der 2 Algorithmus davon ausgehen muss sortierte Daten zu haben.
Das Sortieren der Daten kostet jedoch hier im Beispiel 1600 Zeiteinheiten. Daraus folgt bei einer einzigen Suche sind die Kosten
1600 + 1 * 8 = 1608
Während der erste Algorithmus durchschnittlich für eine Suche die Kosten 100 verursacht.
=> 1608 (Algo2) > 100 (Algo1)
Da die Sortierung nur einmal benötigt wird, armortisiert sich die Sortierung mit der Zeit, durch die verkürzte Suchdauer.
Statt 100 Zeiteinheiten in etwa 8 Zeiteinheiten pro Suche.
-> bei einer einzelnen Suche lohnt sich die Sortierung nicht.
Bei 50 mal Suchen sieht es anders aus.
2000 (Algo2) 1700 (Algo1)
1736 (Algo2) > 1700 (Algo1)
1600 + 18 * 8 (Algo2) [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
ja, jetzt ist es klarer.
Letzte Frage:
Sind dann die amortisierten Kosten die Zahl 18 (Versuche) in diesem Fall oder die 1600, die das Sortieren benötigt ?
Grüße,
Tris
Hallo Tris,
die amortisierten Kosten sind die 1600 für das Sortieren.
Diese Kosten muss der geänderte Algorithmus ersteinmal wieder
einsparen.
Gruss Peter
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
verstehe, also die Kosten, die getilgt werden müssen, sind die amortisierten Kosten.
Nun ist es so, dass häufig eine sog. Potentialfunktion angegeben wird. Was ist die und wie kriegt man die raus ?
Danke und Grüße,
Tris
Hallo Tris,
die amortisierten Kosten sind die 1600 für das Sortieren.
Diese Kosten muss der geänderte Algorithmus ersteinmal wieder
einsparen.
Hi Tris,
der Begriff Potentialfunktion ist eher eng mit der Physik verknüpft.
Man bekommt Kostenfunktionen abhängig von der Menge der Daten und meist noch von der Anzahl der Funktionsaufrufe.
Beispiel für eine Formel:
Grundkosten in Abhängigkeit der Menge von Daten +
(z.B. Sortierung)
Anzahl der Ausführungen * Kosten der Ausführung.
Auch ohne Sortierung kann eine logarithmische Funktion zunächst bei kleinen Datenmengen teurer sein als lineare Funktionen.
400 * log (n) > 20 * n für kleine n.
Meist basieren die Funktionen auf Abschätzungen und bestimmten Annahmen (auch Laufzeittests). Eine Annahme kann sein, das die Zugriffe gleichverteilt sind.
Sind sie nicht gleichverteilt z.B. Telefonbuch und die Nummern die du darin suchst, könnte man ohne Sortierung, bei häufigerer Nutzung, den ersten Algorithmus beschleunigen, indem man die gefundene Nummer ganz oben einordnet. So sind häufig gebrauchte Nummern ziemlich schnell zu finden. Hierbei entstehen zunächst zusätzliche Kosten durch die Änderung der Sortierung. Aber bei häufiger Nutzung armortisieren sich
die Kosten relativ schnell. Bei einer Gleichverteilung profitiert man von der Änderung nicht. Wie du siehst ist es gar nicht so einfach die Kosten eines Algorithmus und damit seine Kostenfunktion festzulegen.
Gruss Peter
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]