Ответ
Нотация Big O (О-нотация) — это математическая нотация, используемая в информатике для описания асимптотической сложности алгоритмов. Она показывает, как время выполнения или потребление памяти алгоритмом растет относительно размера входных данных (n) в худшем случае.
Зачем это нужно? Для сравнения эффективности алгоритмов независимо от конкретного «железа» и для прогнозирования их поведения на больших объемах данных.
Основные классы сложности (от лучшего к худшему):
| Нотация | Название | Описание | Пример на Swift |
|---|---|---|---|
| O(1) | Константная | Время выполнения не зависит от n. |
Доступ к элементу массива по индексу. |
| O(log n) | Логарифмическая | Время растет логарифмически от n. Очень эффективно. |
Бинарный поиск в отсортированном массиве. |
| O(n) | Линейная | Время растет прямо пропорционально n. |
Линейный поиск, перебор массива. |
| O(n log n) | Линейно-логарифмическая | Характерна для эффективных алгоритмов сортировки. | Быстрая сортировка (Quicksort), сортировка слиянием (Mergesort). |
| O(n²) | Квадратичная | Время растет пропорционально квадрату n. Медленно на больших данных. |
Сортировка пузырьком, два вложенных цикла. |
| O(2ⁿ) | Экспоненциальная | Время растет экспоненциально. Неприемлемо для больших n. |
Решение задачи коммивояжера полным перебором. |
Примеры кода:
// O(1) - Константное время
let firstElement = array[0]
// O(n) - Линейное время
for element in array {
print(element)
}
// O(n²) - Квадратичное время (два вложенных цикла)
for i in 0..<n {
for j in 0..<n {
// какая-то операция
}
}
// O(log n) - Логарифмическое время (бинарный поиск)
func binarySearch(_ array: [Int], key: Int) -> Int? {
var low = 0
var high = array.count - 1
while low <= high {
let mid = (low + high) / 2
if array[mid] == key {
return mid
} else if array[mid] < key {
low = mid + 1
} else {
high = mid - 1
}
}
return nil
}Важные принципы анализа:
- Рассматривается худший случай (upper bound).
- Константы отбрасываются. O(2n) записывается как O(n).
- Отбрасываются менее значимые слагаемые. O(n² + n) записывается как O(n²).
Выбор алгоритма с меньшей сложностью Big O критически важен для производительности при работе с большими наборами данных.