DFA到正则表达式的时间复杂度

Question

我在Ullman等人的“自动机理论，语言和计算导论”，第二版，第151页中查看了将DFA转换为正则表达式的时间复杂性分析。此方法有时称为transitive closure method。我不明白他们是如何在O(n^3)*( 4^n ))时间复杂度中想出4^n表达式的。

我知道4^n表达式在空间复杂性方面是成立的，但是，关于时间复杂性，我们似乎在每次迭代中只对每对状态执行四个恒定的时间操作，使用之前迭代的结果。我到底错过了什么？

Answer 1

这是对没有使用正确数据结构的算法的复杂性的粗略限制。我认为除了作者显然不关心在这里进行优化之外，没有什么可解释的，可能是因为他们的主要观点是正则表达式至少和DFA一样有表达能力，而且他们觉得优化这个指数时间算法是没有意义的。

有三个n次迭代的嵌套循环；在外部循环的迭代k期间构造的正则表达式的大小归纳为O(4^k)，因为它们是由前一次迭代期间构造的至多四个正则表达式构造的。如果算法复制这些子表达式，并且我们在所有迭代中高估了O(4^n)的正则表达式大小，那么我们得到O(n^3 4^n)。

显然，我们可以做得更好。在不消除复制的情况下，通过适当地限制几何和，我们可以得到O(sum_{k=1}^ n ^2 4^k) = O (n ^2 (n+ 4^n))。此外，正如您所指出的，我们根本不需要复制，除非在最后我们同意templatetypedef的观点，即输出必须完全写出，为准备正则表达式提供的运行时间为O(n^3)，写出正则表达式的运行时间为O(4^n)。这个版本的空间复杂度等于时间复杂度。