java - 计算非平凡问题的时间复杂度

Question

我在计算如下所示程序的时间复杂度时遇到了麻烦。这是一个生成有效括号的简单程序，例如“（（（）））”“（（）（））”等。但是，我真的不知道如何估计这类问题的时间复杂度。

如果您能在这里分享一些您认为有用的技术，我们将不胜感激。如果您可以分析我作为示例链接的程序，那将是最好的:)

我的目标 ：

1. 估计非平凡程序的时间复杂度。通常是一个有一些修剪的递归程序。

2. 我正在寻找一个快速估计的解决方案，而不是一个严格的数学证明。

先感谢您。

有问题的代码：

public ArrayList<String> generateParenthesis(int n) {
    ArrayList<String> res = new ArrayList<String>();
    String oneSolu = "";

    Generate(n, n, res, oneSolu);

    return res;
}

private void Generate(int l, int r, ArrayList<String> res, String oneSolu) {
    if (l==0 && r==0) {
        res.add(oneSolu);
        return ;
    }

    //add left
    if (l > 0) {
        String t = oneSolu;
        t += "(";
        Generate(l-1, r, res, t);
    }

    if (r>l) {
        String t = oneSolu;
        t += ")";
        Generate(l, r-1, res, t);
    }
}

Answer 1

I have to admit, your particular use case seems particularly tough, so don't be too hard on yourself.

1. Estimate time complexity for nontrivial program. Typically a recursive program which has some pruning.

2. I am looking for a fast estimate solution, not a rigorous mathematical proving.

I can give you my normal thought process when I'm analyzing runtimes. It won't be terribly helpful for this particular case, but can certainly be helpful in the general case (if you run into issues analyzing other programs later on).

I can't give any guarantees about not using rigorous math though; I tend to default to it if I want to be really sure of a bound. For loose bounds, the stuff is generally simple enough to where it's not a big issue though.

---

There's two main things that I generally try to think about first.

1) Can I at least write down the recurrence?

Some recurrences are familiar to a large number of people (like T(n) = T(n-1) + T(n-2)), while some have been studied pretty extensively (like anything solvable with the master method). If a program falls under this category, consider yourself pretty lucky.

In your particular case, the recurrence seems to be something like

T(L,R) = T(L-1,R) + T(L, R-1) if R > L
T(L,R) = T(L-1,R) otherwise, with base case
T(0,R) = R

Not the greatest start.

2) Analyzing how many times a particular function is called with specific arguments

This one is generally more useful in dynamic programming, where past results are stored to save computation, but is also another tool in the belt. That being said, this isn't an option if you can't compute how many times the function is called with specific arguments.

In this case though, this approach gets heavy on the math. The basic problem is that the number of times Generate() is called with a specific l and r depends entirely on the possible values of oneSolu. (The ArrayList is an accumulator, so that's not a worry)

In our case, we happen to know how long the string is (since the first call had l = r = n and each recursive call decreased exactly one of the two by 1), and we can also show that

1. For every value of oneSolu passed in, we can guarantee that every prefix has more (s than )s.
2. Every such string of this specific length is covered.

I'm pretty sure that value can be found, but 1) the math will get ugly very quickly and 2) even if you got that far, you then have to wrap it around a double summation and evaluate that too. Not practical, and even getting this far dealt with way more math than you wanted.

---

Now for the really coarse way to get an upper bound. This is the "quick" way, but it doesn't take into account any sort of pruning, so it can be pretty useless if you want a tight bound. It's already been posted, but I'll add it on anyway so that this answer sums up everything by itself.

3) Multiply the maximum depth by the max branching factor.

As already pointed out by @VikramBhat, you've got a branching factor of 2, and a maximum depth of 2n, so you're looking at a (very very) loose bound of 2²ⁿ = 4ⁿ total nodes, and as pointed out by @KarolyHorvath in the comments, the work per node is going to be linear, so that gives us a O(n4ⁿ) running time.

Answer 2

使用 n 对生成的有效括号数是第 n 个加泰罗尼亚数，定义为2nCn/(n+1)但如果您需要更简化的界限，那么它是O(4^N)。更一般地，任何递归函数的上限是其最大分支因子和深度，就O(b^d)好像在每个级别完成的工作一样O(1)，在这种情况下深度 = 2N，分支因子约为 2，因此T(n) = 2^(2N)=4^N.