时间复杂度 DFA 直接从正则表达式构造

Question

我想知道在龙书中直接使用算法 3.36 从正则表达式中了解 DFA 构造的时间复杂度。

我对外部 while 循环会执行多少次感到困惑？就像在算法中提到的Dstates中一样，它们是否等于正则表达式中的操作数？

另外，在执行等于 |Σ| 次的内部 for 循环中将完成多少工作？

谢谢。

Answer 1

构造的复杂性仍然是 O（2ⁿ）。考虑本文中描述的最坏情况示例：

L = {w ∈ {0,1}*： |w| ≥ n，最后一个符号的第 n 个符号是 1}

语言对应的正则表达式是 （0+1）*1（0+1）...（0+1），其中尾随部分重复 n - 1 次。时间复杂度仍然是O（2 n），因为构造的DFA中的状态数是O（2ⁿ）（对应于L中单词的后缀数）。