java - 这个括号组合的时间复杂度是多少？

Question

实现一个算法来打印 n 对括号的所有有效(又名。正确打开和关闭)组合。
(顺便说一句，这是书 <Cracking coding interview> chp 8，问题 8.9 中的一个问题)

解决方法如下:

括号组合.java:

import java.util.LinkedList;
import java.util.List;

public class ParenthesesCombination {
    /**
     * Find all combinations with n pairs.
     *
     * @param n
     * @return
     */
    public static List<String> getAll(int n) {
        if (n < 1) throw new IllegalArgumentException("n should >= 1, but get: " + n);
        List<String> list = new LinkedList<>();

        getAll(n, n, 0, new char[n * 2], list);

        return list;
    }

    /**
     * Find cases with given buffer & index.
     *
     * @param leftRemaining  left remain count,
     * @param rightRemaining right remain count,
     * @param curIdx         current index in buffer,
     * @param buf            buffer,
     * @param list           result list,
     */
    protected static void getAll(int leftRemaining, int rightRemaining, int curIdx, char[] buf, List<String> list) {
        if (leftRemaining < 0 || rightRemaining < leftRemaining) return; // invalid, discard it,
        if (leftRemaining == 0 && rightRemaining == 0) {
            list.add(String.valueOf(buf)); // found, make a copy, and add,
            return;
        }

        // try to add '(',
        buf[curIdx] = '(';
        getAll(leftRemaining - 1, rightRemaining, curIdx + 1, buf, list);

        // try to add ')',
        buf[curIdx] = ')';
        getAll(leftRemaining, rightRemaining - 1, curIdx + 1, buf, list);
    }
}

示例组合:

pair count: 4, combination count: 14
     0: (((())))
     1: ((()()))
     2: ((())())
     3: ((()))()
     4: (()(()))
     5: (()()())
     6: (()())()
     7: (())(())
     8: (())()()
     9: ()((()))
    10: ()(()())
    11: ()(())()
    12: ()()(())
    13: ()()()()

样本对计数和组合计数为:

1 -> 1
2 -> 2
3 -> 5
4 -> 14
5 -> 42
6 -> 132
7 -> 429

根据算法应该介于:

O(2^n)和 O(4^n)

但是，有没有办法获得更准确的时间复杂度？

Answer 1

精确的输出行数等于加泰罗尼亚数字:https://en.m.wikipedia.org/wiki/Catalan_number .第n个加泰罗尼亚数是Theta(4^n/n^(3/2))，所以运行时间是Theta(4^n/√n)。