Алгоритми та структури даних · Junior · Запитання 63 з 75
Що означає «амортизоване O(1)» для arr.push?
- 1Кожен окремий push гарантовано займає однаковий час
- ✓Правильна відповідь: Рідкісні розширення за O(n) у середньому дають O(1) на push
- 3Push має O(1) лише для масивів, коротших за 1000
Пояснення
Коли внутрішній буфер заповнений, масив виділяє більший (зазвичай приблизно вдвічі) і копіює все. Розмір подвоюється, тож такі копіювання рідкісні, і n вставок разом коштують O(n).