Algorytmy i struktury danych · Junior · Pytanie 63 z 75
Co oznacza „zamortyzowane O(1)” dla arr.push?
- 1Każdy pojedynczy push na pewno trwa tyle samo
- ✓Poprawna odpowiedź: Rzadkie powiększenia O(n) uśredniają się do O(1) na push
- 3Push ma O(1) tylko dla tablic krótszych niż 1000
Wyjaśnienie
Gdy wewnętrzny bufor się zapełni, tablica przydziela większy (zwykle około dwa razy) i kopiuje wszystko. Rozmiar się podwaja, więc takie kopie są rzadkie, a n wstawień kosztuje razem O(n).