정규 표현식의 시간 복잡도

[innerstella]

정규 표현식 엔진은 대부분 **백트래킹(완전탐색 알고리즘)**을 사용하기 때문에, 최악의 경우 시간 복잡도 $O(2^n)$

→ 일반 내장 메서드나 for문보다 성능상 떨어질 수 있음

→ 간단한 로직은 내장 메서드를 활용, 복잡하고 복합적인 로직은 정규 표현식 활용

[[패턴 매칭] 정규표현식](https://velog.io/@ninto_2/정규표현식)

• 백트래킹 : 문제의 조건에 따라 탐색해야 하는 모든 경우의 수를 시도하면서 해를 찾는 알고리즘