Deutsch
Menü

Datenstrukturen und Algorithmen

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?

  1. A2 Sekunden
  2. B8 Sekunden
  3. C32 Sekunden
Antwort und Erläuterung anzeigen

Antwort: B. 8 Sekunden

Bei O(n²) ist die Laufzeit proportional zum Quadrat der Datenmenge; die vierfache Datenmenge braucht also 4² = 16-mal so lange: 0,5 s × 16 = 8 s. 2 Sekunden ergäben sich bei O(n), das proportional zur Datenmenge wächst, und 32 Sekunden bei O(n³), das mit der dritten Potenz wächst (4³ = 64-fach). In der Praxis kann es noch langsamer werden, etwa wenn die Daten nicht mehr in den Cache passen.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. 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?
  2. 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?
  3. 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?
  4. 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?
  5. Der Ausdruck „3 4 + 2 * 5 −“ in umgekehrter polnischer Notation (Postfixnotation) wird ausgewertet, indem jede Zahl auf einen Stack gelegt wird und bei jedem Operator zwei Werte entnommen, verrechnet und das Ergebnis wieder abgelegt wird. Welches Ergebnis entsteht? Der linke Operand eines Operators ist der Wert, der früher abgelegt wurde.