← Назад к вопросам
Что такое "O-большое" (Big O) и для чего оно используется?
1.0 Junior🔥 121 комментариев
#Python Core
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Big O (О-большое): анализ сложности алгоритмов
Big O — это математическая нотация для описания того, как быстро растёт время выполнения (или использование памяти) алгоритма в зависимости от размера входных данных.
Зачем это нужно
Проблема: Как сравнить два алгоритма?
# Алгоритм 1: простой цикл
def algo1(n):
total = 0
for i in range(n):
total += i
return total
# Алгоритм 2: вложенные циклы
def algo2(n):
total = 0
for i in range(n):
for j in range(n):
total += i + j
return total
# Какой лучше? На малых n различие незаметно.
# На больших n algo2 будет намного медленнее.
Big O помогает выразить это математически и предсказать, как алгоритм поведёт себя на больших данных.
Основные классы сложности
O(1) — Константная сложность
Время не зависит от размера входных данных. Операция выполняется за один шаг.
# O(1)
def get_first_element(lst):
return lst[0] # Всегда один доступ, независимо от длины
# O(1)
def dict_lookup(dictionary, key):
return dictionary[key] # Hash table — средняя сложность O(1)
# График: горизонтальная линия
по времени как функция от n = время остаётся одинаковым
O(log n) — Логарифмическая сложность
Время растёт логарифмически. Типично для алгоритмов "разделяй и властвуй".
# O(log n) — бинарный поиск
def binary_search(sorted_lst, target):
left, right = 0, len(sorted_lst) - 1
while left <= right:
mid = (left + right) // 2
if sorted_lst[mid] == target:
return mid
elif sorted_lst[mid] < target:
left = mid + 1 # Отбрасываем половину
else:
right = mid - 1 # Отбрасываем половину
return -1
# Для n=1000000:
# Линейный поиск: ~1000000 операций
# Бинарный поиск: log2(1000000) ≈ 20 операций
# График: медленно растущая кривая
O(n) — Линейная сложность
Время пропорционально размеру входных данных.
# O(n)
def find_max(lst):
max_val = lst[0]
for i in range(1, len(lst)): # Проходим по каждому элементу
if lst[i] > max_val:
max_val = lst[i]
return max_val
# O(n)
def linear_search(lst, target):
for item in lst: # В худшем случае проверяем все элементы
if item == target:
return True
return False
# График: прямая линия, угол 45 градусов
O(n log n) — Линейно-логарифмическая
Типично для хороших алгоритмов сортировки.
# O(n log n) — merge sort
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid]) # Рекурсия (log n уровней)
right = merge_sort(lst[mid:]) # Рекурсия
return merge(left, right) # Слияние O(n)
# На каждом уровне рекурсии делаем O(n) работы
# Уровней рекурсии log(n)
# Итого: O(n log n)
# Для n=1000000:
# O(n log n) ≈ 1000000 * 20 = 20 000 000 операций
O(n²) — Квадратичная сложность
Время растёт как квадрат размера входных данных. Типично для наивных алгоритмов.
# O(n²) — bubble sort
def bubble_sort(lst):
n = len(lst)
for i in range(n): # Цикл 1: n раз
for j in range(n - 1 - i): # Цикл 2: ~n раз
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst
# O(n²)
def check_duplicates(lst):
for i in range(len(lst)): # Цикл 1: n раз
for j in range(i + 1, len(lst)): # Цикл 2: ~n раз
if lst[i] == lst[j]:
return True
return False
# Для n=1000:
# O(n²) = 1000000 операций
# Для n=10000:
# O(n²) = 100000000 операций (100x медленнее)
# График: экспоненциальная парабола
O(n³), O(n⁴), ... — Полиномиальная сложность
# O(n³)
def triple_nested_loop(lst):
n = len(lst)
for i in range(n): # Цикл 1
for j in range(n): # Цикл 2
for k in range(n): # Цикл 3
# Какая-то операция
pass
Очень плохая сложность для больших n. n=100 → 1 млн операций. n=1000 → 1 млрд операций.
O(2^n) — Экспоненциальная сложность
Одна из худших. Время удваивается с каждым увеличением n.
# O(2^n) — неоптимизированная рекурсия Фибоначчи
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2) # Два рекурсивных вызова!
# Вызовы растут как бинарное дерево:
# fib(5)
# / \
# fib(4) fib(3)
# / \ / \
# fib(3) fib(2) fib(2) fib(1)
# ...
# Для n=30: ~1 млн операций
# Для n=50: ~1 триллион операций (невозможно)
# ОПТИМИЗАЦИЯ: O(n) через динамическое программирование
def fibonacci_optimized(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] # Один вызов O(1)
return dp[n]
O(n!) — Факториальная сложность
Самая плохая. Типично для переборных алгоритмов без оптимизации.
# O(n!) — все перестановки (без оптимизации)
def generate_permutations(lst):
if len(lst) <= 1:
return [lst]
result = []
for i in range(len(lst)):
current = lst[i]
remaining = lst[:i] + lst[i+1:]
for perm in generate_permutations(remaining):
result.append([current] + perm) # Каждый вызов порождает n новых
return result
# Для n=10: 3 628 800 перестановок
# Для n=20: 2.4 квинтиллиона перестановок (невозможно за разумное время)
Сравнение графически
Время выполнения
|
O(2^n) \\
\\
\\
O(n³) /\\
/ \\
O(n²) / \\
O(n log n) / |
O(n) / | |
O(log n) /| | | (O(1) на одном уровне)
O(1)-----|------|----
n=1000
Графики по порядку из худшей к лучшей:
O(2^n) > O(n!) > O(n³) > O(n²) > O(n log n) > O(n) > O(log n) > O(1)
Практический пример: сортировка
import time
def bubble_sort(lst): # O(n²)
n = len(lst)
for i in range(n):
for j in range(n - 1 - i):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst
def merge_sort(lst): # O(n log n)
if len(lst) <= 1:
return lst
mid = len(lst) // 2
return merge(merge_sort(lst[:mid]), merge_sort(lst[mid:]))
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Бенчмарк
import random
data = [random.randint(1, 10000) for _ in range(1000)]
start = time.time()
bubble_sort(data.copy())
print(f"Bubble sort (O(n²)): {time.time() - start:.3f}s")
start = time.time()
merge_sort(data.copy())
print(f"Merge sort (O(n log n)): {time.time() - start:.3f}s")
# Результат (примерно):
# Bubble sort (O(n²)): 0.15s
# Merge sort (O(n log n)): 0.003s
# Merge sort в 50 раз быстрее!
Big O для памяти (Space Complexity)
# O(1) space
def sum_array(arr): # Используем только одну переменную
total = 0
for num in arr:
total += num
return total
# O(n) space
def create_copy(arr): # Создаём копию массива
return arr.copy() # Дополнительная память размера n
# O(n²) space
def create_matrix(n):
matrix = []
for i in range(n):
row = [0] * n # Каждая строка — n элементов
return matrix # Итого n² элементов
# O(log n) space для merge sort (рекурсивный стек)
Важные правила Big O
# 1. Игнорируй константы
O(2n) = O(n)
O(100n) = O(n)
O(n + 5) = O(n)
# 2. Игнорируй меньшие члены
O(n² + n) = O(n²) # n² доминирует при больших n
O(n log n + n) = O(n log n)
# 3. O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
# 4. Для циклов — перемножай
for i in range(n): # O(n)
for j in range(n): # O(n)
print(i, j) # O(1)
# Итого: O(n * n * 1) = O(n²)
# 5. Для последовательности — складывай
for i in range(n): # O(n)
print(i)
for j in range(m): # O(m)
print(j)
# Итого: O(n + m)
Практическое применение
Когда выбираешь алгоритм, нужно подумать о size n:
Если n ≤ 10: O(n!) приемлемо
Если n ≤ 100: O(n³) приемлемо
Если n ≤ 1000: O(n²) приемлемо
Если n ≤ 100000: O(n log n) приемлемо
Если n ≤ 1000000: O(n) или O(log n) нужны
Амортизированная сложность
Некоторые операции имеют временную сложность, которая в среднем отличается от худшего случая.
# Динамический массив (как Python list)
my_list = []
for i in range(1000000):
my_list.append(i) # На первый взгляд O(n²)?
# НЕ! Амортизированная сложность O(n)
# Реаллокация памяти происходит редко (в 2x раз при переполнении)
# Средняя операция append имеет O(1) амортизированную сложность
Выводы
Big O — это инструмент для:
- Прогнозирования производительности алгоритма на больших данных
- Сравнения алгоритмов независимо от деталей реализации
- Выбора оптимального решения для задачи с конкретным размером n
- Избежания неоптимальных решений (например, O(2^n) для n > 30)
Всегда думай о Big O при выборе алгоритма — это разница между тем, работает программа за миллисекунду или за час.