Что хотят услышать интервьюеры:

Временная сложность в Big O определяется тем, как растёт число операций при увеличении размера входных данных. Обычно смотрят на доминирующий цикл, вложенность, количество вызовов функций и наличие рекурсий. Важны худший случай и порядок роста, а не точное время выполнения.

Определение:

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

Пример использования:

Если в алгоритме один цикл по n элементам, его сложность обычно O(n). Если внутри цикла есть ещё один цикл по тем же n элементам, получится O(n^2).

def count_pairs(arr):
    count = 0
    for i in range(len(arr)):        # внешний цикл: n
        for j in range(len(arr)):    # внутренний цикл: ещё n
            if arr[i] == arr[j]:
                count += 1
    return count

Здесь число сравнений растёт примерно как n * n, поэтому временная сложность — O(n^2).

Пояснение кода:

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

Ключевые моменты:

Big O зависит от роста количества операций при увеличении входа n.
Основные факторы: циклы, вложенные циклы, рекурсия, вызовы функций, обработка коллекций.
В Big O обычно учитывают худший случай и доминирующий член.
Константы и незначимые слагаемые отбрасываются: O(3n + 10) = O(n).
Сложность нужно оценивать по самой дорогой части алгоритма, а не по отдельным мелким операциям.

Из каких факторов определяется временная сложность алгоритма в нотации Big O?