📦 Розділ 4 · Питання #5

Яка часова складність операцій в ArrayList

Часова складність операцій в ArrayList безпосередньо зумовлена його внутрішньою будовою — неперервним масивом об'єктів Object[] elementData.

📦 Колекції 📄 Вихідний Markdown

🟢 Junior Level

Часова складність операцій в ArrayList безпосередньо зумовлена його внутрішньою будовою — неперервним масивом об’єктів Object[] elementData.

Зведена таблиця часової складності

Операція Складність Опис та чому саме так
get(index) $O(1)$ Миттєво: базова адреса елемента в пам’яті обчислюється за формулою зміщення за 1 такт CPU.
set(index, e) $O(1)$ Миттєвий перезапис посилання за відомим числовим індексом.
add(e) (у кінець) $O(1)^*$ Амортизований константний час. Швидко, але при вичерпанні місткості масиву відбувається ресайз.
add(index, e) $O(N)$ Потрібно зсунути всі елементи правіше індексу на 1 позицію праворуч.
remove(index) $O(N)$ Потрібно зсунути всі елементи правіше індексу на 1 позицію ліворуч.
remove(object) $O(N)$ Пошук елемента через equals() за $O(N)$ плюс зсув решти хвоста масиву за $O(N)$.
contains(e) $O(N)$ Лінійний послідовний перебір усіх елементів масиву.
size() / isEmpty() $O(1)$ Значення розміру зберігається в окремому цілочисельному полі int size.
clear() $O(N)$ Занулення всіх посилань масиву в циклі для запобігання витоку пам’яті. 
ArrayList<String> list = new ArrayList<>();
list.add("Java");      // O(1)* — швидко
list.get(0);          // O(1) — миттєво
list.add(0, "Kotlin");// O(N) — усі елементи зсуваються праворуч
list.remove(0);       // O(N) — усі елементи зсуваються ліворуч
list.contains("Java");// O(N) — послідовний перебір від 0 до size

🟡 Middle Level

1. Математика амортизованої складності $O(1)^*$ для add(e)

Операція додавання в кінець add(e) називається амортизовано константною:

  • У найгіршому випадку: коли внутрішній масив повністю заповнений, операція потребує $O(N)$ часу (виділення нового масиву в 1.5 раза більшого розміру та копіювання всіх наявних $N$ елементів).
  • Математичне обґрунтування: Якщо виконати серію з $N$ додавань у початково порожній список, ресайзи відбудуться лише $\log_{1.5}(N)$ разів. Сумарна вартість усіх копіювань елементів становить збіжну геометричну прогресію: \(\sum \text{копіювань} \le 1.5 \times N = O(N)\)
  • Поділивши сумарний час $O(N)$ на кількість операцій $N$, отримуємо середній час на одне додавання: \(\frac{O(N)}{N} = O(1)\)
Додавання елементів в ArrayList:
[ 1 ][ 2 ][ 3 ][ 4 ] (Capacity = 4)
  │
  ▼ add(5) -> Ресайз: Capacity = 4 * 1.5 = 6
[ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][   ] (Копіювання 4 елементів, вартість O(N))
  │
  ▼ add(6)
[ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ] (Миттєво, вартість O(1))

2. Чому clear() працює за $O(N)$, а не за $O(1)$?

Поширена помилка на співбесідах: вважати, що метод clear() лише скидає лічильник size = 0 за $O(1)$.

Реальний вихідний код OpenJDK:

public void clear() {
    modCount++;
    final Object[] es = elementData;
    for (int to = size, i = (size = 0); i < to; i++)
        es[i] = null; // Занулення посилань!
}

Якби JVM просто скинула size = 0, старий масив elementData продовжував би утримувати сильні посилання на всі видалені об’єкти. Це призвело б до прихованого витоку пам’яті (Memory Loitering): збирач сміття не зміг би вивільнити об’єкти з купи, поки живий сам ArrayList. Тому JVM явно обходить увесь масив і занулює кожну комірку за $O(N)$.

3. Пакетні операції (Bulk Operations)

  • removeIf(Predicate): $O(N)$ у Java 8+. Проходить по масиву за один прохід із двоточковим алгоритмом ущільнення вцілілих елементів. На відміну від наївного циклу з iterator.remove(), що працює за катастрофічні $O(N^2)$, removeIf виконується строго лінійно.
  • addAll(Collection): $O(M)$, де $M$ — розмір колекції, що додається. Масив розширюється рівно один раз під сумарний новий розмір, після чого елементи переносяться за один системний виклик System.arraycopy().
  • sort(Comparator): $O(N \log N)$ з використанням алгоритму TimSort (адаптивне сортування злиттям).

🔴 Senior Level

1. Архітектурний вибір коефіцієнта зростання: чому 1.5x, а не 2x?

У C++ std::vector у деяких стандартних бібліотеках (наприклад, GCC libstdc++) розширюється вдвічі ($2\times$), тоді як у Java ArrayList використовується множник $1.5\times$ (newCapacity = oldCapacity + (oldCapacity >> 1)).

За цим рішенням стоїть оптимізація повторного використання пам’яті та запобігання фрагментації купи:

При коефіцієнті зростання 2x:
Розміри масивів: 1, 2, 4, 8, 16, 32...
Сума всіх попередньо звільнених блоків пам'яті:
1 + 2 + 4 + 8 + 16 = 31 < 32!
Новий масив на 32 елементи НІКОЛИ не поміститься у пам'ять, що звільнилася раніше.
Алокатор операційної системи змушений постійно запитувати нові неперервні сторінки пам'яті,
що призводить до сильної фрагментації купи.

При коефіцієнті зростання 1.5x (або золотого перетину phi ~ 1.618):
Розміри масивів: 10, 15, 22, 33, 49, 73...
Через кілька кроків сума звільнених блоків перевищує розмір наступного необхідного масиву.
Алокатор пам'яті JVM може повторно використати звільнені суміжні блоки пам'яті,
різко знижуючи фрагментацію купи (Heap Fragmentation).

2. Механіка System.arraycopy на рівні апаратного забезпечення

При операціях add(index, e) та remove(index) критично важливо розуміти, що алгоритмічна складність $O(N)$ має надзвичайно низький константний коефіцієнт затримки:

  • Метод System.arraycopy() у HotSpot JVM є спеціальним JVM Intrinsic (компілятор C2 замінює виклик Java на машинну процесорну інструкцію rep movsq або векторні інструкції AVX-256 / AVX-512).
  • Процесор копіює дані блоками по 32 або 64 байти за один машинний такт.
  • Зсув 1 000 елементів займає лише близько 1 мікросекунди.

3. Обмеження пропускної здатності пам’яті (Memory Bandwidth Bottleneck)

Для гігантських колекцій (десятки мільйонів елементів) продуктивність операцій add(0, e) і ресайзів обмежується не обчислювальною потужністю CPU, а фізичною пропускною здатністю шини пам’яті (Memory Bandwidth):

  • Пропускна здатність двоканальної пам’яті DDR4 становить $\sim 25–30$ ГБ/с.
  • Масив на 10 000 000 посилань займає близько 40 МБ.
  • Зсув такого масиву вимагає читання 40 МБ і запису 40 МБ (сумарно 80 МБ трафіку шиною пам’яті), що фізично займає не менше 3–4 мілісекунд чистого простою контролера пам’яті.

🎯 Шпаргалка для інтерв’ю

30-секундна відповідь для співбесіди

«В ArrayList операції читання get() та оновлення set() виконуються за строго константний час $O(1)$. Додавання в кінець add(e) виконується за амортизований час $O(1)^*$, оскільки ресайз із коефіцієнтом $1.5\times$ відбувається експоненційно рідко. Операції вставки та видалення за індексом (add(i, e) та remove(i)), а також пошук contains() виконуються за лінійний час $O(N)$, проте зсуви елементів реалізовані через оптимізований інтринсик System.arraycopy з підтримкою SIMD-інструкцій CPU. Метод clear() має складність $O(N)$, оскільки занулює всі посилання в масиві для коректної роботи збирача сміття».

Питання підвищеної складності з відповідями

  1. Чому add(e) в ArrayList має складність амортизованого $O(1)$, а не чистого $O(1)$? Відповідь: У переважній більшості випадків новий елемент записується в суміжну комірку масиву за індексом array[size++] = e, що займає строго $O(1)$. Але коли місткість масиву вичерпана, JVM змушена створити новий масив в 1.5 раза більшого обсягу і скопіювати туди всі наявні $N$ елементів за час $O(N)$. Оскільки такі розширення відбуваються все рідше й рідше (за геометричною прогресією), сумарні витрати на копіювання при $N$ додаваннях не перевищують $3N$. Усереднюючи ці витрати на $N$ операцій, отримуємо середній (амортизований) час однієї операції $O(1)$.

  2. Яка реальна часова складність методу ArrayList.clear() і чому він не працює за $O(1)$? Відповідь: Складність clear() становить $O(N)$. Якби метод просто скидав лічильник size = 0 за $O(1)$, у внутрішньому масиві Object[] залишилися б старі посилання на об’єкти. Це призвело б до «витоку пам’яті застарілих посилань» (Loitering references): об’єкти не могли б вивільнитися збирачем сміття, поки живий сам ArrayList. Тому метод clear() у циклі явно обходить усі елементи та присвоює коміркам null, що займає $O(N)$ операцій.

  3. Чому в Java обрано коефіцієнт розширення $1.5\times$, тоді як багато реалізацій у C++ використовують $2.0\times$? Відповідь: Коефіцієнт $2.0\times$ гарантує, що розмір кожного нового масиву строго більший за суму всіх попередніх звільнених масивів ($1 + 2 + 4 + … + 2^k < 2^{k+1}$). Це унеможливлює повторне використання вивільненої пам’яті на тій самій ділянці купи, що веде до прогресуючої фрагментації пам’яті. Множник $1.5\times$ дозволяє алокатору JVM уже за кілька циклів ресайзу перевикористовувати блоки пам’яті, що залишилися від старих масивів, запобігаючи фрагментації купи.

  4. Як зробити перевірку наявності contains() в ArrayList швидшою за $O(N)$? Відповідь: Стандартний list.contains() завжди працює за $O(N)$, виконуючи лінійний перебір. Проте якщо список попередньо відсортовано (list.sort(...)), для пошуку можна застосувати алгоритм двійкового пошуку Collections.binarySearch(list, key), який для ArrayList (завдяки маркерному інтерфейсу RandomAccess) знаходить елемент за логарифмічний час $O(\log N)$.

Типові помилки та Red Flags

  • ❌ Стверджувати, що add(e) завжди виконується за $O(1)$. (Забувають про амортизацію та періодичні ресайзи).
  • ❌ Вважати складність clear() рівною $O(1)$. (Нерозуміння роботи збирача сміття та необхідності занулення посилань).
  • ❌ Думати, що ArrayList.remove(0) повільніший за LinkedList.remove(0) на будь-яких обсягах даних. (На невеликих колекціях векторний System.arraycopy в ArrayList випереджає LinkedList через відсутність витрат на деалокацію Node).

Пов’язані теми