반응형
정규식의 복잡성은 무엇입니까?
문자열에 대한 정규식 비교를 수행하는 데 걸리는 문자열 길이와 관련하여 복잡성은 무엇입니까?
대답은 "정규식"이 정확히 무엇을 의미하는지에 따라 다릅니다. 클래식 정규 표현식에이 될 수 컴파일 에 결정적 유한 오토마타 길이의 문자열을 일치시킬 수 있습니다 N에 O(N)시간. 정규식 언어에 대한 특정 확장은 상황을 악화시킵니다.
다음과 같은 관심 문서를 찾을 수 있습니다. 정규식 일치는 간단하고 빠를 수 있습니다 .
제한되지 않음-빈 입력 문자열에서 끝나지 않는 정규식을 만들 수 있습니다.
일반 (TCS : 역 참조 없음, 연결, 대체, Kleene 별) regexp를 사용하고 regexp가 이미 컴파일 된 경우 O (n)입니다.
RegEx에서 (표현식 자체에 관계없이) 엄격한 점근 경계를 찾고 있다면 하나가 없습니다. Alex가 지적했듯이 O (1) 정규식 또는 Omega (infinity) 정규식을 만들 수 있습니다. 순전히 수학적 알고리즘 인 정규식 엔진은 형식적인 점근 분석을 수행하기에는 너무 복잡합니다 (이러한 분석이 기본적으로 가치가 없다는 사실을 제외하면).
특정 표현의 성장률 (실제로는 알고리즘을 구성하기 때문에)은 분석하기가 더 쉽지는 않지만 훨씬 더 의미가 있습니다.
참고 URL : https://stackoverflow.com/questions/4378455/what-is-the-complexity-of-regular-expression
반응형
'Program Tip' 카테고리의 다른 글
| Objective-C의 정방향 선언 열거 (0) | 2020.11.15 |
|---|---|
| 보이지 않는 문자열 값이있는 새 레코드를 데이터 프레임에 추가 할 때 보이지 않는 요인 수준으로 인해 경고가 발생하고 NA가 발생합니다. (0) | 2020.11.15 |
| MongoDB에서 "id"와 "_id"필드의 차이점 (0) | 2020.11.15 |
| 소켓 대 SocketChannel (0) | 2020.11.15 |
| Perl에서 shift ()는 무엇을합니까? (0) | 2020.11.15 |