什么是下一个语法

我正在开发一个广义分析算法，我有一个规则测试它什么是下一个语法

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符号）是我的算法数量。我怎样才能衡量它，因为课程的时间取决于三两件事：

字符串的长度来解析
语法复杂
算法的性能

来源

2012-01-07 yuryeuceda

[程序员.SE]（http://programmers.stackexchange.com/）更适合白板问题（如Big-O分析）。确保你发布足够的算法进行分析。 – outis 2012-01-07 07:51:31

大端O不是测量运行时间的问题;这是剖析。 Big-O是算法分析的问题，如果没有看到算法，这是不可能的。从广义上讲，将算法分解为基本操作，循环和递归调用。基本操作具有定义的时间（通常，O（1））。循环的时间是迭代次数乘以循环体的时间。递归更复杂：您必须根据递归关系定义时间，然后求解显式解决方案。查看process call tree可以提供有关显式解决方案的提示。

来源

2012-01-07 07:43:37 outis

那么，有可能通过它在很多次运行中显示的图表来知道算法的行为（元素的数量与时间或操作的数量），这种算法是一种指数形式，我不喜欢它 – yuryeuceda 2012-01-13 07:00:24

@yuryeuceda：这是剖析，而不是大-O，因为它仅用于特定的输入，可能只代表最好的情况，平均情况或更坏的情况。 Big-O是分析的结果，而不是测量结果。 – outis 2012-01-13 07:30:05

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

任何具有n个叶节点的二叉树可以是一个分析树，并且这样的树的数目由Catalan numbers给出。

来源

2012-01-07 08:18:07

好我是怀疑这个... – yuryeuceda 2012-01-13 07:00:48

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

S ::= a | a S

这将更有效地处理。

来源

2012-01-07 09:48:44

当然！但通过这种方式，我正在改变意义，并记住我正在尝试创建一个算法，我认为这是非常缓慢的方法，因为增长太多了 – yuryeuceda 2012-01-13 06:58:48

什么是下一个语法

回答

相关问题