Какова будет временная сложность подсчета количества всех структурно различных бинарных деревьев?

Question

Используя метод, представленный здесь: http://cslibrary.stanford.edu/110/BinaryTrees.html#java

12. countTrees() Solution (Java)
/**
 For the key values 1...numKeys, how many structurally unique
 binary search trees are possible that store those keys?

 Strategy: consider that each value could be the root.
 Recursively find the size of the left and right subtrees.
*/
public static int countTrees(int numKeys) {
  if (numKeys <=1) {
    return(1);
  }
  else {
    // there will be one value at the root, with whatever remains
    // on the left and right each forming their own subtrees.
    // Iterate through all the values that could be the root...
    int sum = 0;
    int left, right, root;

    for (root=1; root<=numKeys; root++) {
      left = countTrees(root-1);
      right = countTrees(numKeys - root);

      // number of possible trees with this root == left*right
      sum += left*right;
    }

    return(sum);
  }
} 

У меня есть ощущение, что это может быть n (n-1) (n-2) ... 1, то есть n!

При использовании памятника, сложность O (n)?

Answer 1

Число полных двоичных деревьев с числом узлов n - это n-е каталонское число. Каталонские числа рассчитаны как

, что является сложностью O (n).

http://mathworld.wolfram.com/BinaryTree.html

http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics

Answer 2

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

    int C=1;
    for (int i=1; i<=n; i++)
    {
        C = (2*(2*(i-1)+1)*C/((i-1)+2));
    }
    return C;

Обратите внимание на разницу между памяткой и табуляцией здесь

Answer 3

Достаточно просто посчитать количество вызовов на countTrees, который использует этот алгоритм для заданное количество узлов. После нескольких пробных запусков мне кажется, что требуется 5 * 3 ^ (n-2) вызовов для n> = 2, который растет намного медленнее, чем n !. Доказательство этого утверждения оставлено читателю в качестве упражнения. : -)

Запомнившаяся версия потребовала O (n) вызовов, как вы предложили.

Кстати, число бинарных деревьев с n узлами равно n-му каталонскому числу . Очевидные подходы к вычислению C _n кажутся линейными по n, так что запомненная реализация countTrees, вероятно, лучшая из возможных