Większość dopisań trafia w wolne miejsce i kosztuje O(1). Czasem następuje powiększenie i kopiowanie O(n) elementów; rozłożone na wiele dopisań daje średnio O(1) na operację (amortyzacja).
let capacity = 4;
let size = 0;
function append(x: number) {
if (size === capacity) {
capacity *= 2; // resize + copy O(n)
}
size++;
}Dynamiczna tablica ma tablicę bazową z pewnym zapasem capacity. Większość dopisań to zapis do kolejnej wolnej komórki (O(1)). Gdy tablica się zapełni, alokuje większą (często 2x) i kopiuje elementy (O(n)).
Dlaczego amortyzowane O(1)? Bo resize jest rzadki. Przy wzroście przez podwajanie łączny koszt kopiowania dla N dopisań to O(N): każdy element jest przenoszony tylko kilka razy, więc średni koszt dopisania pozostaje stały.
Resizy następują dla rozmiarów 1, 2, 4, 8, 16... Suma kopiowań do N to około 1 + 2 + 4 + ... + N = O(N).
let cap = 4
let size = 0
function append() {
if (size === cap) {
cap *= 2 // alokacja + kopiowanie size elementów (O(size))
}
size += 1 // zapis w wolne miejsce (O(1))
}