 Kostenfunktion für Arrayzugriffe aufstellen |
ubik
Mitglied
Dabei seit: 10.04.2015
Beiträge: 41
 |
|
| Kostenfunktion für Arrayzugriffe aufstellen |
     |
Meine Frage:
Hallo,
folgende Aufgabe:
In vielen Programmiersprachen wird uber Bibliotheken eine dynamische Daten-Struktur Vector angeboten, die den Zugriff auf darin gespeicherte Elemente wie in einem Array über einen Index ermöglicht.
?
Der Zugriff auf eine beliebige Indexposition erfordert Laufzeit O(1). Dies wird meistens dadurch erreicht, dass dieser Typ intern ein Array der initialen Größe m benutzt, dessen Inhalt in ein Array doppelter
Größe kopiert wird, sobald die Kapazitat ausgeschöpft ist. Nach k Verdoppelungen betragt die Große also 2^k * m. Zusatzlich merkt sich ein Vector die nachste freie Index-position und bietet eine Operation append an, die ein Element auf dieser Position ablegt.
(a) Welche Kosten entstehen im worst case, wenn N Elemente mittels append in einen anfangs leeren Vector abgelegt werden sollen, und wieviel reservierter Speicherplatz bleibt ungenutzt? Bitte geben Sie eine genaue Kostenfunktion an, in der die Kosten für das Auslesen oder Zuweisen eines Array-Elementes mit S bezeichnet werden.
Meine Ideen:
Ok.
Soweit so gut.
Die Formel zur Berechnung der freien Felder ist laut mir:
(2^(N-1) * m) / 2
Dann müsste auch die Anzahl der Zugriffe auf den Speicher
T(N) = (2^(N-1) * m) / 2 sein.
Ist das richtig?
|
|
20.04.2015 11:05 |
|
|
ubik
Mitglied
Dabei seit: 10.04.2015
Beiträge: 41
|
|
Hallo,
ja, offensichtlich ist meine Funktion falsch.
Aber deine verstehe ich auch nicht ganz.
Sei N = 10 Elemente und sei m = 1.
Dann ergibt sich für k:
log_2 (10 / 1) = 1 ????
Die Anzahl der Verdopplungen ist also 1?
Es werden doch mehr Elemente verdoppelt:
1 Element belegt → erstelle 1 freies Element, somit 1 freies Element
2 Elemente belegt → erstelle 2 freie Elemente, somit 2 freie Elemente
3 Elemente belegt – 1 Element frei
4 Elemente belegt – 0 Elemente frei → erstelle 4 freie Elemente
5 Elemente belegt – 3 freie Elemente
6 Elemente belegt – 2 freie Elemente
7 Elemente belegt – 1 freies Element
8 Elemente belegt → erstelle 8 freie Elemente
9 Elemente belegt, 7 Elemente frei
10 Elemente belegt, 6 Elemente frei
|
|
|
01.05.2015 09:28 |
|
|
|
|
| Zitat: |
| log_2 (10 / 1) = 1 |
Wo hast du das denn her, richtig wäre 3.32192809488736
Und das gibt aufgerundet 4, also 4 Verdopplungen.
Das deckt sich auch mit deiner Aufzählung.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
01.05.2015 09:49 |
|
|
ubik
Mitglied
Dabei seit: 10.04.2015
Beiträge: 41
|
|
Oh, ja. Mein Taschenrechner...
Ok, alles klar.
Danke!
|
|
|
01.05.2015 13:50 |
|
|
|
