Kostenfunktion für Arrayzugriffe aufstellen

Neue Frage »

Auf diesen Beitrag antworten »
ubik 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?
 
Auf diesen Beitrag antworten »
eulerscheZahl

Zitat:
Die Formel zur Berechnung der freien Felder ist laut mir:
(2^(N-1) * m) / 2

Das heißt, bei einer Anfangsgröße von 1 und 10 hinzugefügten Einträgen hast du 256 freie Felder?!
Die Gesamtgröße wäre 16, somit bleiben 6 freie Felder.

Allgemein: bei N Elementen und einem Gesamtspeicher von [latex]m\cdot 2^k[/latex] bei k Verdopplungen:
[latex]N \leq m\cdot 2^k[/latex], was umgestellt nach k ergibt:
[latex]k=\left\lceil \log_2\left(\frac{N}{m}\right) \right\rceil[/latex] (Die eckigen Klammern stehen für die ceil-Funktion, also "Aufrunden")
Für die Anzahl der freien Felder musst du von [latex]m\cdot 2^k[/latex] noch N abziehen.

Deine Speicherzugriffszahl ist auch zu hoch. Beim Verdoppeln ist diese meiner Meinung nach (ohne Gewähr) das doppelte der alten Größe (aus dem alten Array lesen und in das neue schreiben). Ansonsten ist 1 Zugriff zum Schreiben nötig. Die Gesamtzahl hängt also vom oben errechneten k ab.
Auf diesen Beitrag antworten »
ubik

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
Auf diesen Beitrag antworten »
eulerscheZahl

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.
 
Auf diesen Beitrag antworten »
ubik

Oh, ja. Mein Taschenrechner...

Ok, alles klar.

Danke!
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »