Какова сложность следующей грамматики

Question

Я разрабатываю обобщенный алгоритм анализа и проверяю его по следующему правилу

S ::= a | SS

Ну, алгоритм показывает мне все деревья, сгенерированные для строки, состоящей из n a.

Например, следующая таблица показывает время, используемое алгоритмом из-за количества 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 (обозначение Big O) мой алгоритм. Как я могу измерить это, потому что, конечно, время зависит от трех вещей:

1. Длина строки для разбора
2. Грамматическая сложность
3. Производительность алгоритма

Answer 1

S может соответствовать любой строке из всех a.

Любое двоичное дерево с n конечными узлами может быть деревом разбора, и число таких деревьев определяется каталонскими числами .

Answer 2

Мы не знаем сложности, потому что вы не опубликовали алгоритм. Но, очевидно, есть шанс, что у вас будет очень плохая реализация. Проблема не обязательно в алгоритме, мысли, но в самой грамматике. Подходящий препроцессор для грамматики может переписать его в более естественную форму

S ::= a | a S

, который был бы намного более эффективным в обращении.

Answer 3

Big-O - это не вопрос измерения времени работы; это профилирование. Big-O - это вопрос анализа алгоритма, который невозможно увидеть без алгоритма.

Вообще говоря, разбейте алгоритм на базовые операции, циклы и рекурсивные вызовы. Основные операции имеют определенное время (как правило, O (1)). Время цикла - это число итераций, умноженное на время тела цикла. Рекурсия сложнее: вы должны определить время в терминах рекуррентного отношения, а затем решить для явного решения. Глядя на дерево вызовов процесса , можно получить подсказки о том, каким может быть явное решение.