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

Нужно уметь оценить, как время выполнения решения растёт с увеличением размера входных данных. Обычно ожидают не просто назвать O(...), а объяснить, от чего именно зависит сложность и почему. Важно различать лучший, средний и худший случаи, если это влияет на оценку.

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

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

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

Если в коде есть один проход по массиву из n элементов, временная сложность обычно O(n).

func sum(_ numbers: [Int]) -> Int {
    var total = 0
    for number in numbers {
        total += number
    }
    return total
}

Здесь количество операций растёт линейно с размером массива: если элементов в 2 раза больше, работа примерно тоже увеличится в 2 раза.

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

Код нужен, потому что пример связан с анализом алгоритма.
Шаги:

Создаётся счётчик total.
Затем цикл проходит по каждому элементу массива ровно один раз.
Для каждого элемента выполняется постоянное число операций: сложение и присваивание.
Поэтому итоговая сложность — O(n).

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

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

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

Какова временная сложность решения в нотации O?