Какие структуры данных имеют сложность O(1)?

Что такое O(1) и почему это важно?

O(1) обозначает константную временную сложность — время выполнения операции не зависит от количества элементов в структуре данных. Это идеальный показатель производительности, к которому стремятся при проектировании алгоритмов.

Основные структуры с O(1)

• Массив: доступ к элементу по индексу — O(1). Например, arr[5] сразу возвращает значение, так как адрес вычисляется как базовый_адрес + индекс * размер_элемента.
• Хеш-таблица: вставка, удаление и поиск в среднем случае — O(1). Ключ преобразуется в индекс через хеш-функцию, что позволяет быстро найти нужную ячейку.
• Стек и очередь: добавление и удаление элементов с одного конца (стек) или с разных концов (очередь) — O(1).

Примеры кода

// Массив: доступ по индексу O(1)
const arr = [10, 20, 30];
console.log(arr[1]); // 20

// Хеш-таблица (объект): поиск O(1)
const map = { 'a': 1, 'b': 2 };
console.log(map['a']); // 1

// Стек: push/pop O(1)
const stack = [];
stack.push(1);
stack.pop();

Вывод

Структуры с O(1) критичны для задач, где важна скорость обработки больших объёмов данных. Их стоит применять при реализации кэшей, быстрых поисковых систем и операций с фиксированным временем отклика.