정규식의 복잡성은 무엇입니까?
정규식의 복잡성은 무엇입니까? 문자열에 대한 정규식 비교를 수행하는 데 걸리는 문자열 길이와 관련하여 복잡성은 무엇입니까? 대답은 "정규식"이 정확히 무엇을 의미하는지에 따라 다릅니다. 클래식 정규 표현식에이 될 수 컴파일 에 결정적 유한 오토마타 길이의 문자열을 일치시킬 수 있습니다 N에 O(N)시간. 정규식 언어에 대한 특정 확장은 상황을 악화시킵니다. 다음과 같은 관심 문서를 찾을 수 있습니다. 정규식 일치는 간단하고 빠를 수 있습니다 . 제한되지 않음-빈 입력 문자열에서 끝나지 않는 정규식을 만들 수 있습니다. 일반 (TCS : 역 참조 없음, 연결, 대체, Kleene 별) regexp를 사용하고 regexp가 이미 컴파일 된 경우 O (n)입니다. RegEx에서 (표현식 자체에 관계없이) 엄격..