Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

正则表达式的复杂度

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


只有注册用户登录后才能发表评论。


网站导航: