Ответ
Big O нотация — это математическая запись, которая описывает верхнюю границу (худший случай) роста времени выполнения или потребления памяти алгоритма в зависимости от размера входных данных (обозначаемого как n). Она позволяет абстрагироваться от констант и конкретного "железа", чтобы сравнивать фундаментальную эффективность алгоритмов.
Основные классы сложности (от лучшего к худшему):
-
O(1) — Константная: Время выполнения не зависит от
n.// Доступ к элементу массива по индексу int value = array[42]; -
O(log n) — Логарифмическая: Время растёт логарифмически. Характерно для алгоритмов, которые на каждом шаге делят задачу пополам.
// Бинарный поиск в отсортированном массиве while (low <= high) { int mid = low + (high - low) / 2; if (array[mid] == target) return mid; if (array[mid] < target) low = mid + 1; else high = mid - 1; } -
O(n) — Линейная: Время растёт прямо пропорционально
n.// Линейный поиск, обход связного списка for (int i = 0; i < array.length; i++) { if (array[i] == target) return i; } -
O(n log n) — Линейно-логарифмическая: Часто встречается у эффективных алгоритмов сортировки.
// Сортировка слиянием (Merge Sort), быстрая сортировка (QuickSort) в среднем случае -
O(n²) — Квадратичная: Время растёт пропорционально квадрату
n. Типично для простых алгоритмов с вложенными циклами.// Сортировка пузырьком (Bubble Sort) for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { ... } }
Зачем это нужно: Выбор алгоритма с оптимальной сложностью становится критичным при работе с большими объемами данных. Операция O(n²) на миллионе элементов выполняется триллионы раз дольше, чем O(n log n).
