Какие знаешь типы сложности алгоритмов?

Типы сложности алгоритмов

Времени и пространственная сложность — ключевые метрики для оценки эффективности алгоритмов. Я регулярно анализирую сложность при выборе подходящего решения для задачи.

Big O Notation (Большой O)

Это стандартная нотация для описания асимптотической сложности. Показывает, как алгоритм масштабируется с ростом входных данных.

Основные типы временной сложности

1. O(1) — Константная сложность

Цепочка операций не зависит от размера входных данных:

def get_first_element(arr):
    return arr[0]  # O(1)

def add_numbers(a, b):
    return a + b  # O(1)

Примеры: доступ к элементу массива по индексу, операции со словарем, простые арифметические операции

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  # O(log n)

Примеры: бинарный поиск, сбалансированные деревья поиска, логарифмическое разбиение

3. O(n) — Линейная сложность

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

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1  # O(n)

def find_max(arr):
    max_val = arr[0]
    for num in arr:  # O(n)
        if num > max_val:
            max_val = num
    return max_val

Примеры: простой поиск, итерация по массиву, обход связного списка

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

Частое встречается в эффективных алгоритмах сортировки:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])  # O(log n) уровней
    right = merge_sort(arr[mid:])
    return merge(left, right)  # O(n) операций слияния

Примеры: merge sort, quick sort, heap sort

5. O(n²) — Квадратичная сложность

Два вложенных цикла по элементам:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr  # O(n²)

Примеры: bubble sort, insertion sort, поиск всех пар

6. O(2^n) — Экспоненциальная сложность

Делится на две подзадачи в каждом рекурсивном вызове:

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
    # O(2^n) без мемоизации

Примеры: рекурсивные алгоритмы без оптимизации

Пространственная сложность

Описывает дополнительную память, используемую алгоритмом:

# O(1) — константная память
x = 5
y = 10

# O(n) — линейная память
new_array = [0] * n

# O(n²) — квадратичная память
matrix = [[0] * n for _ in range(n)]

Сравнение временных сложностей

Наилучше:

• O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n)

Для n = 1,000,000:

• O(1): 1 операция
• O(log n): примерно 20 операций
• O(n): 1,000,000 операций
• O(n log n): примерно 20,000,000 операций
• O(n²): 1 триллион операций

Практические рекомендации

• O(1), O(log n), O(n) — отличные алгоритмы
• O(n log n) — хороший выбор для больших данных
• O(n²) — приемлемо для n < 10,000
• O(n³) — используйте только для n < 500
• O(2^n), O(n!) — избегайте для реальных приложений

В своей работе я всегда анализирую сложность перед написанием кода и выбираю оптимальный алгоритм для конкретной задачи.