Что такое временная сложность алгоритма?

Что такое временная сложность алгоритма

Временная сложность — это мера количества базовых операций, которые алгоритм выполняет в зависимости от размера входных данных. Она показывает, как время выполнения растет с увеличением входных данных.

Основное понимание

Временная сложность не измеряет время в секундах — она считает количество операций:

def find_sum(arr):
    total = 0           # 1 операция
    for i in range(len(arr)):
        total += arr[i]  # выполняется n раз
    return total        # 1 операция

# Всего операций: 1 + n + 1 = n + 2
# Упрощаем, игнорируя константы: O(n)

Как считать операции

Правила:

1. Простые операции (присваивание, арифметика): 1 операция
2. Цикл: количество итераций умножить на операции внутри
3. Вложенные циклы: перемножить количество итераций
4. Игнорировать константы: O(2n) = O(n)
5. Игнорировать младшие члены: O(n^2 + n) = O(n^2)

Примеры анализа

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

def get_element(arr, index):
    return arr[index]  # Одна операция, не зависит от размера

# Операций: 1, независимо от размера массива

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

def find_max(arr):
    max_val = arr[0]        # 1 операция
    for i in range(1, len(arr)):  # n-1 итераций
        if arr[i] > max_val:      # 1 операция в итерации
            max_val = arr[i]      # 1 операция
    return max_val           # 1 операция

# Операций: 1 + (n-1)*2 + 1 = 2n
# Упрощаем: O(n)

O(n^2) — квадратичная сложность

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):           # n итераций
        for j in range(n - i - 1):  # n итераций
            if arr[j] > arr[j + 1]:  # 1 операция
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 1 операция

# Операций: n * n * 2 = 2n^2
# Упрощаем: O(n^2)

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

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:         # log(n) итераций
        mid = (left + right) // 2  # 1 операция
        if arr[mid] == target:
            return mid             # 1 операция
        elif arr[mid] < target:
            left = mid + 1         # 1 операция
        else:
            right = mid - 1        # 1 операция

# Операций: log(n) * 4
# Упрощаем: O(log n)
# Почему log(n)? Каждый раз делим массив пополам

O(n log n) — линеарифметическая сложность

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # T(n/2)
    right = merge_sort(arr[mid:])     # T(n/2)
    
    return merge(left, right)          # O(n)

# T(n) = T(n/2) + T(n/2) + O(n)
# Решение: O(n log n)
# Почему? Глубина рекурсии = log(n), на каждом уровне O(n) работы

Важные категории

Поддиапазон сложности O(n):

# O(n) + O(n) = O(n) — последовательные циклы
for i in range(n):
    print(i)
for i in range(n):
    print(i)

# O(n^2) — вложенные циклы
for i in range(n):
    for j in range(n):
        print(i, j)

# O(n^3) — три вложенных цикла
for i in range(n):
    for j in range(n):
        for k in range(n):
            print(i, j, k)

Практические примеры

Поиск дубликатов:

# Наивный подход: O(n^2)
def has_duplicates_naive(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# Оптимизированный подход: O(n)
def has_duplicates_optimized(arr):
    seen = set()
    for num in arr:
        if num in seen:
            return True
        seen.add(num)
    return False

Факториал:

# Рекурсивный: O(n)
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

# Итеративный: O(n)
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Амортизированная сложность

Иногда операция кажется дорогой, но в среднем дешевая:

# Dynamic array (список в Python)
arr = []
for i in range(n):
    arr.append(i)  # Кажется O(n), но амортизированная O(1)

# Почему? Массив растет динамически, переаллокация редкая

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

Аналогично временной, но для памяти:

# O(1) память
def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

# O(n) память
def create_copy(arr):
    return arr.copy()  # Создает новый массив размером n

# O(n^2) память
def create_matrix(n):
    matrix = [[0] * n for _ in range(n)]  # n * n элементов
    return matrix

Best Practices

1. Анализируй худший случай — это Big O
2. Ищи циклы и рекурсию — основные источники сложности
3. Игнорируй константы — O(2n) = O(n)
4. Выбирай правильный алгоритм — O(n) намного лучше O(n^2)

Понимание временной сложности критично для написания масштабируемого и эффективного кода.