Числовая оценка сложности алгоритмов: шпаргалка
Введение
Числовая оценка сложности алгоритмов, или "Big O Notation", помогает понять, как быстро будет работать алгоритм с увеличением размера данных. В этой шпаргалке мы разберем наиболее распространенные случаи и упрощение выражений для оценки.
Основные оценки
Оценка сложности
| Оценка | Описание |
|---|---|
| O(1) | Доступ по индексу в массиве |
| O(n) | Проход по массиву с помощью foreach |
| O(log n) | Бинарный поиск |
| O(n log n) | Сортировка слиянием |
| O(n²) | Проход по массиву внутри другого прохода |
| O(n³) | Тройной вложенный проход |
| O(2^n) | Числа Фибоначчи |
| O(n!) | Обход графа |
Упрощение оценок
Иногда выражения можно упростить, чтобы легче понять их сложность. Вот несколько примеров:
Примеры упрощений
- O(2n) → O(n)
Экспоненциальный коэффициент не влияет на порядок. - O(n + n²) → O(n²)
Сложность определяется самым "дорогим" элементом. -
O(n²/2) → O(n²)
Константы убираются из анализа. -
O(n + log n) → O(n)
Логарифмические изменения незначительны по сравнению с линейными. -
O(60 * 2^n + 10*n^100) → O(2^n)
Главное влияние на сложность оказано экспоненциальным ростом. -
O(n² + m) → O(n² + m)
Тут оценивается параллельная сложность двух переменных.
Заключение
Понимание "Big O Notation" поможет вам оценивать эффективность ваших алгоритмов в зависимости от размера данных. Эта шпаргалка — полезный ресурс для быстрого ориентирования в сложностях алгоритмов.
При создании эффективных программ важно использовать эти знания, чтобы минимизировать время выполнения и ресурсы.