下一个语法的复杂度是多少
我正在开发一个通用解析算法，并使用下一个规则对其进行测试。
S ::= a | SS
好吧，该算法向我展示了为由 n a 组成的字符串生成的所有树。
例如，下一个表显示了由于 a 的数量而导致算法使用的时间，
length trees time(ms)
1 1 1
2 1 1
3 2 2
4 5 2
5 14 2
6 42 2
7 132 5
8 429 13
9 1430 28
10 4862 75
11 16796 225
12 58786 471
13 208012 1877
14 742900 10206
我不知道 O （大 O 表示法）是我的算法。我如何衡量它，因为时间当然取决于三个因素：
- 要解析的字符串的长度
- 语法复杂性
- 算法的性能
I'm developing a Generalized Parsing Algorithm and I'm testing it with next rule
S ::= a | SS
Well, the algorithm is showing me all trees generated for the string composed of n a's.
For example next table shows the time used by the algorithm due to the quantity of a's
length trees time(ms)
1 1 1
2 1 1
3 2 2
4 5 2
5 14 2
6 42 2
7 132 5
8 429 13
9 1430 28
10 4862 75
11 16796 225
12 58786 471
13 208012 1877
14 742900 10206
I dont know what O (Big O notation) is my algorithm. How can i measure it because of course the time depends of three things:
- The length of the string to parse
- The grammar complexity
- The performance of the algorithm
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
S 可以匹配所有 a 的任意字符串。
任何具有 n 个叶节点的二叉树都可以是解析树，并且此类树的数量由 Catalan 数字给出。
S can match any string of all a's.
Any binary tree with n leaf nodes could be a parse tree, and the number of such trees is given by the Catalan numbers.
Big-O 不是测量运行时间的问题；而是测量运行时间的问题。这就是剖析。 Big-O是算法分析的问题，不看算法是不可能的。
一般来说，将算法分解为基本操作、循环和递归调用。基本操作具有定义的时序（通常为 O(1)）。循环的计时是迭代次数乘以循环体的计时。递归比较棘手：您必须根据递归关系定义时间，然后求解显式解决方案。查看进程调用树 可以提供有关显式解决方案可能是什么的提示。
Big-O isn't a matter of measuring run-times; that's profiling. Big-O is a matter of algorithm analysis, which is impossible without seeing the algorithm.
Broadly speaking, break the algorithm down into basic operations, loops and recursive calls. The basic operations have a defined timing (generally, O(1)). The timing of loops is the number of iterations times the timing of the loop body. Recursion is trickier: you have to define the timing in terms of a recurrence relation, then solve for an explicit solution. Looking at the process call tree can offer hints as to what the explicit solution might be.
我们也不知道复杂性，因为您没有发布算法。但显然，你的实现有可能会非常糟糕。问题不一定出在算法、思想上，而是出在语法本身。合适的语法预处理器可以将其重写为更自然的形式
，这样处理起来会更有效。
We don't know the complexity neither because you didn't post the algorithm. But obviously there is a chance that you have an implementation that blows up pretty bad. The problem is not necessarily in the algorithm, thought, but in the grammar itself. A suitable preprocessor for the grammar could rewrite it to the more natural form
which would be much more efficient to handle.