Классы сложности алгоритмов

Подробное объяснение основных классов сложности и их практическое применение.

Основные классы сложности

Big-O нотация описывает, как время выполнения алгоритма растёт с увеличением размера входных данных. Это позволяет сравнивать алгоритмы и выбирать оптимальный для конкретной задачи.

O(1)Константная

Время выполнения не зависит от размера данных.

Примеры:

Доступ к элементу массива по индексу
Добавление элемента в конец массива
Получение размера структуры данных

O(log n)Логарифмическая

Очень быстро растёт. При удвоении данных время увеличивается всего на одну операцию.

Примеры:

Бинарный поиск в отсортированном массиве
Поиск в сбалансированном бинарном дереве
Операции в куче (heap)

O(n)Линейная

Время растёт пропорционально размеру данных. Удвоение данных = удвоение времени.

Примеры:

Линейный поиск в массиве
Проход по всем элементам массива
Поиск максимума/минимума

O(n log n)Линейно-логарифмическая

Хорошая сложность для сортировок. Практически оптимально для сравнения элементов.

Примеры:

Быстрая сортировка (в среднем)
Сортировка слиянием
Сортировка кучей

O(n²)Квадратичная

Медленно для больших данных. Удвоение данных = увеличение времени в 4 раза.

Примеры:

Пузырьковая сортировка
Сортировка выбором
Вложенные циклы по массиву

O(2ⁿ)Экспоненциальная

Очень медленно, практически неприменимо для больших данных.

Примеры:

Перебор всех подмножеств
Некоторые задачи оптимизации
Рекурсивные алгоритмы без мемоизации

Практические примеры

Сравнение сложностей на массиве из 1,000,000 элементов:

O(1) — 1 операция
O(log n) — ~20 операций
O(n) — 1,000,000 операций
O(n log n) — ~20,000,000 операций
O(n²) — 1,000,000,000,000 операций

Видно, что разница между O(n) и O(n²) огромна! Поэтому важно выбирать правильный алгоритм.

НазадЧто такое алгоритм ВпередКак оценивать сложность алгоритма

Полезные темы

Рекомендуем изучить эти темы для лучшего понимания