Posted on 2008-03-27 00:21
ZelluX 阅读(1672)
评论(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大小
大概是这样子吧