Deutsch
Menü

Datenstrukturen und Algorithmen

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)?

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
Antwort und Erläuterung anzeigen

Antwort: C. O(n²)

Die Zahl der verglichenen Paare beträgt (n−1) + (n−2) + … + 1 = n(n−1)/2, also 45 bei n = 10 und 499.500 bei n = 1000. Die O-Notation beschreibt nur, wie der Aufwand bei großem n wächst; daher entfallen der Faktor 1/2 und der Term niedrigerer Ordnung, und es ergibt sich O(n²). Verdoppelt sich n, vervierfacht sich die Zahl der Vergleiche ungefähr. O(n) ist die Komplexität eines Verfahrens, das jedes Element einmal betrachtet, und O(n log n) die von Verfahren wie Mergesort, die die Daten wiederholt halbieren.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. 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?
  2. 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?
  3. Welche Aussage beschreibt eine verkettete Liste (eine Liste, in der jedes Element einen Zeiger auf das nächste Element enthält) im Vergleich zu einem Array richtig?
  4. Auf einem leeren Stack werden nacheinander die Operationen push 1, push 2, pop, push 3, push 4, pop, pop ausgeführt. In welcher Reihenfolge werden die Werte durch pop entnommen?
  5. In eine leere Warteschlange (Queue) werden die Elemente A, B und C in dieser Reihenfolge eingefügt. Dann wird ein Element entnommen, D eingefügt und ein Element entnommen, E eingefügt und ein Element entnommen. In welcher Reihenfolge werden die Elemente entnommen?