Algorithmen und Datenstrukturen · Junior · Frage 63 von 75
Was bedeutet „amortisiert O(1)“ für arr.push?
- 1Jedes einzelne push dauert garantiert gleich lange
- 2Seltene O(n)-Vergrößerungen mitteln sich auf O(1) pro push
- 3push ist nur bei Arrays unter 1.000 Elementen O(1)
Antwort zeigen
Richtige Antwort: Seltene O(n)-Vergrößerungen mitteln sich auf O(1) pro push
Erklärung
Ist der interne Puffer voll, belegt das Array einen größeren (meist etwa doppelt so groß) und kopiert alles. Weil sich die Größe verdoppelt, sind diese Kopien selten, und die Gesamtkosten von n pushes sind O(n).