Ответ
Алгоритмическая сложность (Big O нотация) — это способ описать, как время выполнения алгоритма или объем используемой памяти растут с увеличением размера входных данных (n). Она оценивает наихудший или типичный сценарий, отбрасывая константы и менее значимые части.
Зачем это нужно в Python: Для выбора оптимального алгоритма или структуры данных при работе с большими объемами данных, чтобы избежать проблем с производительностью.
Основные классы сложности (от лучшего к худшему):
| Нотация | Название | Пример в Python | Описание роста |
|---|---|---|---|
| O(1) | Константная | my_dict[key] |
Время не зависит от n |
| O(log n) | Логарифмическая | Бинарный поиск | Растет очень медленно |
| O(n) | Линейная | for item in list: |
Пропорционально n |
| O(n log n) | Линейно-логарифмическая | Эффективные сортировки (Timsort) | Хорошо для сортировки |
| O(n²) | Квадратичная | Вложенные циклы | Медленно для больших n |
| O(2ⁿ) | Экспоненциальная | Рекурсивный Фибоначчи (наивный) | Крайне медленно |
Практические примеры на Python:
# O(1) - Константное время (доступ по индексу в списке, ключу в словаре)
def get_first_element(items):
return items[0] # Всегда одна операция
# O(n) - Линейное время (проход по списку)
def find_item(items, target):
for item in items: # В худшем случае n итераций
if item == target:
return True
return False
# O(n²) - Квадратичное время (пузырьковая сортировка, вложенные циклы)
def find_pairs(items):
pairs = []
for i in range(len(items)): # n раз
for j in range(i + 1, len(items)): # ~n/2 раз в среднем
pairs.append((items[i], items[j])) # Итог ~ n²
return pairs
# O(log n) - Логарифмическое время (бинарный поиск)
def binary_search(sorted_list, target):
low, high = 0, len(sorted_list) - 1
while low <= high:
mid = (low + high) // 2
if sorted_list[mid] == target:
return mid
elif sorted_list[mid] < target:
low = mid + 1 # Отбрасываем половину массива
else:
high = mid - 1 # Отбрасываем половину массива
return -1
# Каждый шаг уменьшает область поиска вдвое. Для n=1_000_000 нужно ~20 шагов.Вывод для разработчика: При выборе между list и set для проверки наличия элемента (if x in collection), важно помнить, что операция in для списка имеет сложность O(n), а для множества (set) — O(1) в среднем случае. Для больших данных это решающее отличие.
