我正在研究 Ullman 等人在第 2 版第 151 页的“自动机理论、语言和计算简介”中将 DFA 转换为正则表达式的时间复杂度分析。这种方法有时被称为传递闭包方法。我不明白他们是如何在 O((n^3)*(4^n)) 时间复杂度中提出 4^n 表达式的。
我知道 4^n 表达式关于空间复杂度是成立的,但是,关于时间复杂度,似乎我们在每次迭代中只对每对状态执行四个恒定时间操作,使用之前迭代的结果。我到底错过了什么?
我正在研究 Ullman 等人在第 2 版第 151 页的“自动机理论、语言和计算简介”中将 DFA 转换为正则表达式的时间复杂度分析。这种方法有时被称为传递闭包方法。我不明白他们是如何在 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}^nn^2 4^k) = O(n^2 (n + 4^n))。此外,正如您所指出的,我们根本不需要复制,除非最后我们同意 templatetypedef 输出必须完全写出,运行时间为 O(n^3) 来准备正则表达式和 O(4^n) 写出来。这个版本的空间复杂度等于时间复杂度。
我想你的疑问是关于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 Expression
Conversion具有相同的复杂性。同样的方法也可以用于转换NFA
和ε-NFA
对应的正则表达式。
的主要问题transitive closure approach
是它创建了非常大的正则表达式。这个大的长度是由于连接项的重复联合。