Что такое Big-O нотация? Что такое O(1), O(n), O(n²)?

Что такое Big-O

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

Нотация не измеряет точное количество миллисекунд. Она помогает сравнивать алгоритмы и понимать, как они будут вести себя на больших объёмах данных.

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

Операция выполняется за примерно одинаковое число шагов независимо от размера данных.

def get_first_item(items):
    return items[0]

Получение элемента массива по индексу обычно имеет сложность O(1).

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

Количество операций растёт пропорционально числу элементов. Если данных станет в два раза больше, работы будет примерно в два раза больше.

def find_max(items):
    maximum = items[0]

    for item in items:
        if item > maximum:
            maximum = item

    return maximum

Чтобы найти максимум в неотсортированном списке, нужно в худшем случае проверить все n элементов.

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

Квадратичная сложность часто возникает при двух вложенных циклах по одним и тем же данным. При увеличении числа элементов в два раза объём работы становится примерно в четыре раза больше.

def print_all_pairs(items):
    for first in items:
        for second in items:
            print(first, second)

Если в списке n элементов, функция обработает примерно n × n пар.

Что обычно игнорируют в Big-O

При оценке обычно игнорируют константы и слагаемые меньшего порядка. Например, O(2n + 10) упрощают до O(n), а O(n² + n) — до O(n²).

Как ответить на собеседовании

Big-O описывает, как растут время или память алгоритма при росте входных данных. O(1) не зависит от размера данных, например доступ к элементу массива по индексу. O(n) означает один проход по данным, а O(n²) часто появляется при двух вложенных циклах.