Ответ
Нотация "O" большое (Big O Notation) — это математическая нотация, которая описывает асимптотическую верхнюю границу скорости роста времени выполнения или потребления памяти алгоритма в худшем случае при увеличении размера входных данных n.
Ключевая идея: Оценивает эффективность алгоритма, а не его точное время в секундах. Она показывает, как масштабируется алгоритм.
Основные классы сложности (от лучшего к худшему):
| Нотация | Название | Пример | Описание роста |
|---|---|---|---|
| O(1) | Константная | Доступ к элементу массива по индексу | Не зависит от n |
| O(log n) | Логарифмическая | Бинарный поиск | Растет очень медленно |
| O(n) | Линейная | Поиск в неотсортированном массиве | Пропорционально n |
| O(n log n) | Линейно-логарифмическая | Эффективные алгоритмы сортировки (QuickSort, MergeSort) | Немного хуже линейного |
| O(n²) | Квадратичная | Сортировка пузырьком, два вложенных цикла | Быстро ухудшается |
| O(2ⁿ) | Экспоненциальная | Решение задачи коммивояжера полным перебором | Неприемлемо для больших n |
Правила упрощения ("почему" отбрасываем константы и младшие степени): Big O описывает рост при n → ∞. Поэтому:
- Отбрасываем константы:
O(5n + 10)→O(n). - Оставляем самую быстрорастущую функцию:
O(n² + n log n + 1000)→O(n²). - Игнорируем основание логарифма:
O(log₂ n)→O(log n).
Практические примеры на Java:
// O(1) - Константное время
int getFirst(int[] arr) {
return arr[0]; // Одна операция
}
// O(n) - Линейное время
boolean contains(int[] arr, int key) {
for (int num : arr) { // Цикл по n элементам
if (num == key) return true;
}
return false;
}
// O(n²) - Квадратичное время (пузырьковая сортировка)
void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) { // Внешний цикл: n итераций
for (int j = 0; j < n - 1; j++) { // Внутренний цикл: ~n итераций
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1); // Итого: n * n = n² операций
}
}
}
}
// O(log n) - Логарифмическое время (бинарный поиск)
int binarySearch(int[] sortedArr, int key) {
int left = 0, right = sortedArr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Делим диапазон пополам
if (sortedArr[mid] == key) return mid;
if (sortedArr[mid] < key) left = mid + 1;
else right = mid - 1;
} // На каждой итерации область поиска уменьшается ВДВОЕ
return -1;
}Зачем это нужно? Big O — это язык для обсуждения компромиссов между скоростью и памятью. Выбор алгоритма с лучшей асимптотикой (O(n log n) вместо O(n²)) становится критичным при обработке больших данных.