NFA 的复杂性
Complexity of an NFA
我在多个来源（例如 1, 2 - 第 160 页）中看到，运行 通过 NFA 的复杂度为 O(m²n)。但是我一直不明白为什么会这样。
我的直觉是复杂度应该是O(m^n)（其中m是字符串的长度，n是状态数），因为对于输入字符串中的每个字母，有n NFA 可以转向他们的可能状态。
谁能给我解释一下？
谢谢。
让我们想想我们将如何做一步模拟NFA。我们从一组活动状态 Qinit 开始。对于我们所处的每个状态，我们查看所有标有当前符号的传出转换，然后将它们收集到一个集合 Qmid 中。接下来，我们从这些状态追踪所有可能的 ε-转换，并不断重复这个过程，直到没有更多的 ε-转换可以跟随（也就是说，我们找到 ε-闭包），给我们新的状态集 Q下一个。然后，我们对输入中的每个字符重复此过程一次。
那么这需要多少时间？好吧，输入字符串中有 m 个字符，所以 运行 时间是我们对一个字符所做的工作的 m 倍。每个状态最多可以有 n 个转换，将其留在每个字符上，因此迭代 Qinit 中的所有字符以找到集合 Qmid[=26 的时间=]是O(n2)：Qinit中有O(n)个状态，我们只需要扫描O(n)个转换每个州。从那里开始，我们必须继续跟踪 ε-transitions，直到我们 运行 out of transitions to follow。我们可以通过从 Qmin 中的每个状态同时开始并且仅遵循 ε-转换来执行 BFS 或 DFS 来做到这一点。 NFA 最多可以有 O(n2) 个 ε-transitions 总数（每对状态之间有一个），因此 BFS 或 DFS 将 运行 及时 O(n 2)。总体而言，我们每个字符的工作量为 O(n2)，因此完成的总工作量为 O(mn2).
我在多个来源（例如 1, 2 - 第 160 页）中看到，运行 通过 NFA 的复杂度为 O(m²n)。但是我一直不明白为什么会这样。
我的直觉是复杂度应该是O(m^n)（其中m是字符串的长度，n是状态数），因为对于输入字符串中的每个字母，有n NFA 可以转向他们的可能状态。
谁能给我解释一下？
谢谢。
让我们想想我们将如何做一步模拟NFA。我们从一组活动状态 Qinit 开始。对于我们所处的每个状态，我们查看所有标有当前符号的传出转换，然后将它们收集到一个集合 Qmid 中。接下来，我们从这些状态追踪所有可能的 ε-转换，并不断重复这个过程，直到没有更多的 ε-转换可以跟随（也就是说，我们找到 ε-闭包），给我们新的状态集 Q下一个。然后，我们对输入中的每个字符重复此过程一次。
那么这需要多少时间？好吧，输入字符串中有 m 个字符，所以 运行 时间是我们对一个字符所做的工作的 m 倍。每个状态最多可以有 n 个转换，将其留在每个字符上，因此迭代 Qinit 中的所有字符以找到集合 Qmid[=26 的时间=]是O(n2)：Qinit中有O(n)个状态，我们只需要扫描O(n)个转换每个州。从那里开始，我们必须继续跟踪 ε-transitions，直到我们 运行 out of transitions to follow。我们可以通过从 Qmin 中的每个状态同时开始并且仅遵循 ε-转换来执行 BFS 或 DFS 来做到这一点。 NFA 最多可以有 O(n2) 个 ε-transitions 总数（每对状态之间有一个），因此 BFS 或 DFS 将 运行 及时 O(n 2)。总体而言，我们每个字符的工作量为 O(n2)，因此完成的总工作量为 O(mn2).