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

Question

实现一种算法来打印n对括号的所有有效(又称正确打开和关闭)组合.
(顺便说一句,这是第<Cracking coding interview>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).