Какая временная сложность алгоритма проверки скобок в одну проходку?

Question

Алгоритм проверки скобок за один проход работает за O(n), где n — длина строки. Мы проходим по каждому символу ровно один раз. Операции со стеком (append и pop) выполняются за постоянное время. Поэтому суммарно время линейное.

YeaHub · Accepted Answer

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