Какие знаешь методы оценки сложности алгоритма

Оценка сложности алгоритма выполняется с помощью Big-O нотации, которая описывает верхнюю границу времени выполнения или использования памяти в худшем случае. Основные методы оценки:

1. Анализ количества операций – подсчёт элементарных действий (сравнения, присваивания и т.д.) в зависимости от размера входных данных.
2. Асимптотический анализ – оценка поведения алгоритма при больших n, игнорируя константы и меньшие члены.

Примеры сложностей:

• O(1) – константная (доступ к элементу массива).
• O(n) – линейная (проход по списку).
• O(n²) – квадратичная (вложенные циклы).

# O(n) – линейная сложность
def linear_search(arr, target):
    for item in arr:  # n операций
        if item == target:
            return True
    return False

# O(n²) – квадратичная сложность
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]

Также учитывают Ω (лучший случай) и Θ (средний случай), но Big-O – основной инструмент.