Вопрос проверяет базовое понимание оценки эффективности алгоритмов и умение обосновать сложность по количеству операций.
Алгоритм проверки скобок за один проход работает за O(n), где n — длина строки. Мы проходим по каждому символу ровно один раз. Операции со стеком (append и pop) выполняются за постоянное время. Поэтому суммарно время линейное.
Временная сложность O(n) означает, что время работы растёт пропорционально размеру входных данных.
Перед подсчётом полезно разложить алгоритм на атомарные действия:
Есть один цикл по строке длиной n
На каждой итерации выполняется ограниченное число операций:
Проверка типа символа
Возможный append в стек
Возможный pop из стека
Сравнение типов скобок
Так как на каждый символ — константная работа, суммарно это O(n).
Память в худшем случае — O(n), когда строка состоит только из открывающих скобок, и все они оказываются в стеке.
Это оптимально для этой задачи: нельзя гарантированно проверить корректность, не посмотрев на каждый символ хотя бы раз.
Линейный проход хорошо масштабируется на длинных строках.
Однопроходная проверка скобок имеет O(n) по времени и O(n) по памяти в худшем случае, что является стандартным и эффективным решением.
