Приведи примеры сложности алгоритмов

Сложность алгоритмов: Big O нотация

Big O — это способ оценить, как растёт время выполнения алгоритма в зависимости от размера входных данных. Давайте посмотрим на примеры.

Основные уровни сложности (от быстрого к медленному)

O(1) — Константное время

Лучший случай — не зависит от размера данных:

# O(1) — всегда одна операция
def get_first_element(arr):
    return arr[0]

# O(1) — словарь/hash map
dictionary = {"key": "value"}
value = dictionary["key"]  # Мгновенно, независимо от размера

# O(1) — проверка в set
users_set = {"alice", "bob", "carol"}
if "alice" in users_set:  # Мгновенно
    print("Found")

O(log n) — Логарифмическая

Каждая итерация уменьшает размер задачи в 2 раза:

# O(log n) — бинарный поиск
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1  # Отсекли половину!
        else:
            right = mid - 1  # Отсекли половину!
    
    return -1

# Примеры:
# N = 1000 → максимум 10 итераций
# N = 1000000 → максимум 20 итераций
# log₂(1000000) ≈ 20

Другие примеры O(log n):

# Работа с бинарным деревом
class TreeNode:
    def find(self, value):  # O(log n) если дерево сбалансировано
        if self.value == value:
            return self
        elif value < self.value:
            return self.left.find(value)
        else:
            return self.right.find(value)

# Операции в heap
heap.push(item)  # O(log n)
heap.pop()      # O(log n)

O(n) — Линейная

Время растёт пропорционально размеру входа:

# O(n) — простой поиск
def find_max(arr):
    max_value = arr[0]
    for element in arr:  # Проходим все элементы
        if element > max_value:
            max_value = element
    return max_value

# O(n) — copy list
new_list = arr.copy()  # Копируем каждый элемент

# O(n) — sum
total = sum(arr)  # Суммируем все элементы

# O(n) — find in list
if value in arr:  # Проходим список, пока не найдём
    print("Found")

O(n log n) — Линейно-логарифмическая

Самые эффективные алгоритмы сортировки:

# O(n log n) — merge sort
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # log n слоёв
    right = merge_sort(arr[mid:])     # log n слоёв
    
    return merge(left, right)  # O(n) на каждом слое

# O(n log n) — quicksort (в среднем)
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]
    left = [x for x in arr if x < pivot]      # O(n)
    middle = [x for x in arr if x == pivot]   # O(n)
    right = [x for x in arr if x > pivot]     # O(n)
    
    return quicksort(left) + middle + quicksort(right)  # log n слоёв

# Практика:
import heapq
heapq.heapsort(arr)  # O(n log n)

from collections import Counter
Counter(arr).most_common(k)  # O(n log k)

O(n²) — Квадратичная

Вложенные циклы — очень медленно:

# O(n²) — bubble sort (плохой)
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):           # n итераций
        for j in range(n - 1):    # n итераций внутри
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# O(n²) — поиск пары с суммой
def find_pairs_with_sum(arr, target):
    pairs = []
    for i in range(len(arr)):        # n итераций
        for j in range(i + 1, len(arr)):  # n итераций
            if arr[i] + arr[j] == target:
                pairs.append((arr[i], arr[j]))
    return pairs

# O(n²) — матрица (Гаусс)
def matrix_multiplication(A, B):
    result = []
    for i in range(len(A)):       # n
        row = []
        for j in range(len(B[0]))  # n
            sum_val = 0
            for k in range(len(B)):  # n
                sum_val += A[i][k] * B[k][j]
            row.append(sum_val)
        result.append(row)
    return result  # O(n³)!

O(2ⁿ) — Экспоненциальная

Чрезвычайно медленно для больших N:

# O(2ⁿ) — рекурсивный Фибоначчи (БЕЗ мемоизации)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # Два рекурсивных вызова!

# Дерево вызовов:
# fib(5) = fib(4) + fib(3)
#        = (fib(3) + fib(2)) + (fib(2) + fib(1))
#        = (fib(2) + fib(1)) + (fib(1) + fib(0)) + ...
# Много повторений! 2^5 = 32 вызова для fib(5)

# Проблемы:
# N = 10: быстро
# N = 20: 1 секунда
# N = 30: 1 час
# N = 40: столетие

# O(2ⁿ) с мемоизацией → O(n)
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

fib_memo(100)  # Мгновенно!

O(n!) — Факториальная

Абсолютно невозможно для N > 15:

# O(n!) — перебрать все перестановки
from itertools import permutations

def generate_all_permutations(arr):
    return list(permutations(arr))

# Примеры:
# N = 5: 120 перестановок (быстро)
# N = 10: 3.6 миллиона (можно)
# N = 12: 479 миллионов (медленно)
# N = 15: ∞ (компьютер завис)

# O(n!) — решить задачу коммивояжёра перебором
def tsp_brute_force(cities):
    min_distance = float('inf')
    for perm in permutations(cities):
        distance = calculate_total_distance(perm)
        min_distance = min(min_distance, distance)
    return min_distance

# Для 12 городов: 12! = 479 миллионов перестановок

Практический пример: поиск дубликатов

O(n²) — наивный подход:

def find_duplicates_slow(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# Для 10,000 элементов: 50 миллионов сравнений

O(n) — с хеш-сетом:

def find_duplicates_fast(arr):
    seen = set()
    for element in arr:
        if element in seen:  # O(1)
            return True
        seen.add(element)    # O(1)
    return False

# Для 10,000 элементов: 10,000 операций

Как выбирать алгоритм

# Задача: отсортировать 1 миллион элементов

# O(n²): bubble sort
# Время: 10^12 операций = 1000+ секунд (не подходит!)

# O(n log n): merge sort
# Время: 10^6 × 20 = 20 миллионов операций = 0.02 секунд ✅

# Вывод: O(n log n) в миллион раз быстрее!

Шпаргалка для интервью

Лучшие алгоритмы:

• O(1) — hash lookup, array access
• O(log n) — binary search, balanced trees
• O(n) — linear search, simple iteration
• O(n log n) — merge sort, efficient sorting

Избегайте:

• O(n²) — nested loops (unless necessary)
• O(2ⁿ) — exponential (use memoization)
• O(n!) — permutations (impossible for N > 15)

Оптимизация:

1. Профилируйте реальные данные
2. Используйте правильные структуры (dict vs list)
3. Кэшируйте повторные вычисления
4. Разделяй и властвуй (divide & conquer)
5. Динамическое программирование для O(2ⁿ)