我正在研究 Ullman 等人在第 2 版第 151 页的“自动机理论、语言和计算简介”中将 DFA 转换为正则表达式的时间复杂度分析。这种方法有时被称为传递闭包方法。我不明白他们是如何在 O((n^3)*(4^n)) 时间复杂度中提出 4^n 表达式的。
我知道 4^n 表达式关于空间复杂度是成立的，但是，关于时间复杂度，似乎我们在每次迭代中只对每对状态执行四个恒定时间操作，使用之前迭代的结果。我到底错过了什么？
问问题
1960 次
2 回答
2
这是对未使用正确数据结构的算法复杂性的粗略限制。除了作者显然不想在这里优化之外，我认为没有什么要解释的，可能是因为他们的主要观点是正则表达式至少与 DFA 一样具有表达力，并且因为他们认为优化这个指数毫无意义时间算法。
有三个嵌套循环，每个循环有 n 次迭代；在外循环的迭代 k 期间构造的正则表达式归纳地具有 O(4^k) 的大小，因为它们是由最多四个在前一次迭代期间构造的正则表达式构造的。如果算法复制了这些子表达式，并且我们高估了所有迭代的正则表达式大小限制在 O(4^n)，那么我们得到 O(n^3 4^n)。
显然我们可以做得更好。在不消除复制的情况下，我们可以通过适当地限制几何和得到 O(sum_{k=1}^nn^2 4^k) = O(n^2 (n + 4^n))。此外，正如您所指出的，我们根本不需要复制，除非最后我们同意 templatetypedef 输出必须完全写出，运行时间为 O(n^3) 来准备正则表达式和 O(4^n) 写出来。这个版本的空间复杂度等于时间复杂度。
于 2013-05-21T12:24:51.093 回答
0
我想你的疑问是关于n 3时间复杂度。
让我们假设R ij k表示将自动机从状态 q i转换到q j而不通过任何高于q k的状态的所有字符串的集合。
那么R ij k的迭代公式如下所示，
R ij k = R ik k-1 (R kk k-1 ) * R kj k-1 + R ij k-1。
这种技术类似于全对最短路径问题。唯一的区别是我们采用正则表达式的并集和连接，而不是对距离求和。所有对最短路径问题的时间复杂度为n 3。DFA因此，我们也可以预期to Regular ExpressionConversion具有相同的复杂性。同样的方法也可以用于转换NFA和ε-NFA对应的正则表达式。
的主要问题transitive closure approach是它创建了非常大的正则表达式。这个大的长度是由于连接项的重复联合。
于 2013-04-22T05:34:37.897 回答