我正在查看将 DFA 转换为正则表达式的时间复杂度分析 “Introduction to the Automata Theory, Languages and Computation”，第 2 版，第 151 页，作者:Ullman 等人。此方法有时称为 transitive closure method .我不明白他们是怎么想出 O((n^3)*(4^n)) 时间复杂度的 4^n 表达式的。
我知道 4^n 表达式在空间复杂度方面成立，但在时间复杂度方面，似乎我们在每次迭代中使用先前迭代的结果对每对状态仅执行四个常数时间操作。我究竟缺少什么？
最佳答案
这是对未使用正确数据结构的算法的复杂性的粗略限制。我认为除了作者显然不关心在这里进行优化之外，没有什么可以解释的，可能是因为他们的主要观点是正则表达式至少与 DFA 一样具有表现力，并且因为他们认为优化这个指数毫无意义-时间算法。
共有三个嵌套循环，每个循环 n 次；在外循环的第 k 次迭代期间构造的正则表达式的大小归纳为 O(4^k)，因为它们最多由前一次迭代期间构造的四个正则表达式构造而成。如果算法复制这些子表达式，并且我们高估了所有迭代的 O(4^n) 的正则表达式大小界限，那么我们得到 O(n^3 4^n)。
显然我们可以做得更好。在不消除复制的情况下，我们可以通过适本地限制几何和来得到 O(sum_{k=1}^n n^2 4^k) = O(n^2 (n + 4^n)) 。此外，正如您所指出的，我们根本不需要复制，除非最后我们同意 templatetypedef 输出必须完全写出，给出 O(n^3) 的运行时间来准备正则表达式和 O(4^n) 来写出来。此版本的空间复杂度等于时间复杂度。
关于regex - DFA 到正则表达式的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16095230/