什麼是下一個語法

我正在開發一個廣義分析算法，我有一個規則測試它什麼是下一個語法

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

什麼是下一個語法

回答

相關問題