Ответ
Алгоритмическая сложность, описываемая Big O нотацией — это математическая оценка эффективности алгоритма, показывающая, как время выполнения или потребление памяти алгоритма растет с увеличением размера входных данных (n).
Зачем это нужно: Для предсказания поведения алгоритма на больших данных и выбора наиболее оптимального решения.
Основные классы сложности (от лучшего к худшему):
| Нотация | Название | Пример | Описание роста |
|---|---|---|---|
| O(1) | Константная | Доступ к элементу массива по индексу. | Не зависит от n. |
| O(log n) | Логарифмическая | Бинарный поиск в отсортированном массиве. | Растет очень медленно. |
| O(n) | Линейная | Линейный поиск, обход массива. | Пропорционально n. |
| O(n log n) | Линейно-логарифмическая | Эффективные алгоритмы сортировки (QuickSort, MergeSort). | Немного быстрее, чем квадратичная. |
| O(n²) | Квадратичная | Пузырьковая сортировка, вложенные циклы. | Быстро растет при увеличении n. |
| O(2ⁿ) | Экспоненциальная | Решение задачи коммивояжера полным перебором. | Непригодно для больших n. |
Практические примеры на Swift:
1. O(1) — Константное время:
func getFirstElement(from array: [Int]) -> Int? {
return array.first // Всегда одна операция
}2. O(n) — Линейное время:
func findValue(_ value: Int, in array: [Int]) -> Int? {
for (index, element) in array.enumerated() { // Цикл по n элементам
if element == value {
return index
}
}
return nil
}3. O(n²) — Квадратичное время:
func printAllPairs(in array: [Int]) {
for i in 0..<array.count { // n итераций
for j in 0..<array.count { // n итераций для каждой i
print("((array[i]), (array[j]))") // Всего ~n² операций
}
}
}4. O(log n) — Логарифмическое время (Бинарный поиск):
func binarySearch(_ value: Int, in sortedArray: [Int]) -> Int? {
var low = 0
var high = sortedArray.count - 1
while low <= high {
let mid = (low + high) / 2
if sortedArray[mid] == value {
return mid
} else if sortedArray[mid] < value {
low = mid + 1 // Отбрасываем левую половину
} else {
high = mid - 1 // Отбрасываем правую половину
}
}
return nil
}
// Каждый шаг уменьшает область поиска вдвое. Для n=16 нужно не более 4 шагов (log₂(16)=4).Важные правила анализа Big O:
- Константы игнорируются: O(5n) → O(n).
- Слагаемые меньшего порядка игнорируются: O(n² + n) → O(n²).
- Анализируется наихудший случай (worst-case).
- Пространственная сложность анализируется аналогично, но для потребляемой памяти.
Выбор алгоритма с оптимальной асимптотической сложностью — ключевой фактор для производительности приложений, работающих с большими объемами данных.