时间复杂度权衡nfa vs dfa [英] time complexity trade offs of nfa vs dfa

问题描述

（我发现答案，它的下面在任何人的评论）

(i found the answer, its below in comments for anyone else)

我正在寻找一个更好的使用和在编译器的什么情况下的讨论nfa或dfa。什么是模拟nfa vs dfa的时间复杂度折中，哪一个更适合在编译器的什么情况下？

i am looking for a discussion on which is better used and in what circumstanes in a compiler an nfa or dfa. what are the time complexity trade offs of simulating an nfa vs dfa and which one is more suitable during what circumstances in a compiler??

谢谢你，考试和帮助将非常麻烦：）

Thank you, im revising for a college exam and help would be greatly apriciated :)

Leanne。有人回答我:(：）

Leanne. somebody answer me :( :)

推荐答案

• 来自NFA的DFA的构建时间是O （2 ^ m）其中m是节点数。


• DFA的运行时间是O（n），其中n是输入字符串的长度。这是因为对于给定字符串，只有一条路径通过DFA。


• NFA的构建时间应为O（m），其中m是节点数量


• NFA的运行时间为O（m²n），因为它是非确定性的，计算机必须检查字符串中当前字符的每个可能路径。 （假设没有前瞻，它不知道下一个字符将是什么，所以它运行到死胡同）


• The construction time for a DFA from an NFA is O(2^m) where m is the number of nodes.
• The running time of a DFA is O(n) where n is the length of the input string. This is because there is only 1 path through the DFA for a given string.
• The construction time for an NFA should be O(m), where m is the number of nodes
• The running time for an NFA is O(m²n) because it is non-deterministic and the computer must check every possible path for the current character in the string. (assuming no lookahead, it doesn't know what the next character will be so it runs into dead ends)

这些数字可能给ua简介

These figures might give u a brief idea

这篇关于时间复杂度权衡nfa vs dfa的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！