Deutsch
Menü

Datenstrukturen und Algorithmen

Ein dynamisches Array legt, wenn ein Element hinzugefügt wird, während es voll ist, einen neuen Bereich mit doppelter Kapazität an und kopiert alle Elemente dorthin. Wie viele Elementkopien entstehen insgesamt, wenn einem leeren Array mit der Kapazität 1 nacheinander 1000 Elemente hinzugefügt werden?

  1. A10
  2. B1023
  3. C499.500
Antwort und Erläuterung anzeigen

Antwort: B. 1023

Die Kapazität verdoppelt sich jedes Mal, wenn sie erschöpft ist, also 1, 2, 4, …, 512, und jedes Mal werden alle vorhandenen Elemente kopiert; die Gesamtzahl der Kopien beträgt daher 1 + 2 + 4 + … + 512 = 1023. Bei 1000 Hinzufügungen ist das etwa eine Kopie pro Element, der Aufwand pro Hinzufügen ist im Mittel also konstant: amortisiert O(1). Wüchse die Kapazität jedes Mal nur um 1, ergäben sich 1 + 2 + … + 999 = 499.500 Kopien, also O(n²). 10 ist die Zahl der Neuanlagen des Speicherbereichs, nicht die Zahl der kopierten Elemente.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Warum ist bei einer Hashtabelle mit vielen Elementen und einem Belegungsfaktor von etwa 0,5 die offene Adressierung mit linearem Sondieren am ehesten schneller als die Verkettung (Verbinden der Elemente durch verkettete Listen)?
  2. Für das Sortieren auf paralleler Hardware wie GPUs werden manchmal Sortierverfahren mit einer festen Folge von Vergleichs- und Tauschschritten (Sortiernetzwerke) wie Bitonic Sort verwendet. Warum?
  3. Welche Zeitkomplexität hat bei einem Array mit n Elementen ein Verfahren, das jedes Paar zweier verschiedener Elemente genau einmal vergleicht (eine doppelte Schleife, die das i-te Element mit allen dahinterliegenden Elementen vergleicht und i schrittweise erhöht)?
  4. Ein Programm mit der Zeitkomplexität O(n²) benötigt für 1000 Datenelemente 0,5 Sekunden. Wie lange benötigt es etwa für 4000 Datenelemente?
  5. Eine lineare Suche vergleicht die Elemente eines Arrays mit 100 verschiedenen Werten der Reihe nach von vorn, um einen Zielwert zu finden. Der Zielwert ist immer im Array enthalten und steht mit gleicher Wahrscheinlichkeit an jeder Position. Wie viele Vergleiche sind im Mittel nötig?