0

我正在开发一个通用解析算法，我正在使用下一条规则对其进行测试

S ::= a | SS

好吧，该算法向我展示了为由n a's 组成的字符串生成的所有树。

例如，下表显示了算法使用的时间，因为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

我不知道O我的算法是什么（大 O 表示法）。我如何测量它，因为时间当然取决于三件事：

  1. 要解析的字符串的长度
  2. 语法复杂度
  3. 算法的性能
4

3 回答 3

1

S 可以匹配所有 a 的任何字符串。

任何具有 n 个叶节点的二叉树都可以是解析树，这种树的数量由加泰罗尼亚数字给出。

于 2012-01-07T08:18:07.360 回答
0

Big-O 不是测量运行时间的问题。这就是剖析。Big-O是算法分析的问题，不看算法是不可能的。

从广义上讲，将算法分解为基本操作、循环和递归调用。基本操作具有定义的时间（通常为 O(1)）。循环的时间是迭代次数乘以循环体的时间。递归更棘手：您必须根据递归关系定义时间，然后求解显式解决方案。查看进程调用树可以提供关于显式解决方案可能是什么的提示。

于 2012-01-07T07:43:37.197 回答
0

我们也不知道复杂性，因为您没有发布算法。但很明显，您有可能有一个非常糟糕的实现。问题不一定出在算法上，思想上，而在语法本身。适合语法的预处理器可以将其重写为更自然的形式

S ::= a | a S

处理起来会更有效率。

于 2012-01-07T09:48:44.733 回答