Posted on 2008-03-27 00:21
ZelluX 閱讀(1693)
評論(0) 編輯 收藏 所屬分類:
Algorithm
其實理解了?Regular Expression?-> NFA -> DFA 這個過程，大致的復雜度確定也不難
發信人: styc (styc), 信區: Algorithm
標? 題: Re: 請問一下大家正則表達式的時間復雜度
發信站: 水木社區 (Wed Mar 26 20:37:02 2008), 站內
NFA構造O(n)，匹配O(nm)
DFA構造O(2^n)，最小化O(kn'logn')（N'=O(2^n)），匹配O(m)
n=regex長度，m=串長，k=字母表大小，n'=原始的dfa大小
大概是這樣子吧