Algorithmen und Datenstrukturen · Junior · Frage 21 von 75
Warum kann eine Queue aus push und shift bei großen Eingaben langsam werden?
- 1
shiftverschiebt alle verbleibenden Elemente, das ist O(n) - 2
pushkopiert jedes Mal das ganze Array - 3Arrays in JavaScript fassen nicht mehr als 10.000 Elemente
Antwort zeigen
Richtige Antwort: shift verschiebt alle verbleibenden Elemente, das ist O(n)
Erklärung
Jedes shift indiziert den Rest des Arrays neu, n Elemente zu entnehmen kann also insgesamt O(n²) kosten. Bei starker Nutzung hält man einen Head-Index und liest arr[head++], oder nutzt eine verkettete Liste oder einen Ringpuffer.