정규표현식의 계산복잡도 자료 있을까요?

재미있어보이네요.

제 생각에는 복잡도의 기준이 필요할 것 같습니다.

단순히 과부하를 위해 과금이 필요하다면 시간에 적당히 비례하면 될 것 같고,

과부하와 관계없이 정규표현식의 복잡도를 따진다면, 해당언어의 grep코드를 분석해야 할 것 같습니다.
grep이 while문 같은 조건식으로 되어있을테고, 얼마나 많은 루프를 시작하는지 체크하거나 하는 방법도 생각해 볼 수 있을 것 같습니다.
짧게 생각해보면 정규표현식이 몇개의 덩어리로 검색이 되는지 생각해보면 좋을 것 같네요.

아니면, 얼마나 구체적으로 찾으려고 하는지, \w+로 찾을 걸 abc로 찾는지 그런 기준이나,
아예 역으로 전체 내용과 결과에 따라 정규표현식의 복잡도를 추론해 볼 수도 있을것 같네요.

어쨌든 정규표현식 과금이라 왠지 아주 중요한 정보를 검색하는 일 같군요. 궁금궁금....