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

我不得不承认，您的特定用例似乎特别棘手，所以不要对自己太苛刻。

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.

我可以告诉你我在分析运行时时的正常思维过程。对于这种特殊情况，它不会有太大帮助，但在一般情况下肯定会有帮助(如果您稍后在分析其他程序时遇到问题)。

不过，我不能保证不使用严格的数学；如果我想真的确定一个界限，我倾向于默认使用它。对于松散边界，这些东西通常很简单，但不是什么大问题。

---

我通常首先尝试考虑两件主要事情。

1) 我至少可以写下重复发生的次数吗？

很多人都熟悉一些递归(比如 T(n) = T(n-1) + T(n-2))，而一些已经被广泛研究(比如任何可以用 master 方法解决的问题) ).如果某个程序属于此类，那您就很幸运了。

在您的特定情况下，重复似乎是这样的

T(L,R) = T(L-1,R) + T(L, R-1) 如果 R > L
T(L,R) = T(L-1,R) 否则，使用基本情况
T(0,R) = R

这不是最好的开始。

2) 分析使用特定参数调用特定函数的次数

这个通常在动态规划中更有用，在动态规划中存储过去的结果以节省计算，但它也是腰带中的另一种工具。也就是说，如果您无法计算使用特定参数调用该函数的次数，则这不是一个选项。

不过，在这种情况下，这种方法对数学的要求很高。基本问题是次数 Generate()使用特定的 l 调用和 r完全取决于 oneSolu 的可能值. (ArrayList 是一个累加器，所以不用担心)

在我们的例子中，我们碰巧知道字符串有多长(因为第一次调用有 l = r = n 并且每次递归调用恰好将两者中的一个减 1)，我们还可以证明

1. 对于 oneSolu 的每个值传入，我们可以保证每个前缀都有更多(比) s.
2. 每个这个特定长度的字符串都被覆盖了。

我很确定可以找到这个值，但是 1) 数学会很快变得很丑陋，并且 2) 即使你做到了那么远，你也必须将它包裹在一个双重求和中并评估 也是。不切实际，即使走到这一步，也需要比你想要的更多的数学知识。

---

现在是获得上限的粗略方法。这是“快速”的方式，但它没有考虑任何形式的修剪，所以如果你想要一个紧密的界限，它可能毫无用处。它已经发布，但无论如何我都会添加它，以便这个答案本身总结所有内容。

3) 将最大深度乘以最大分支因子。

正如@VikramBhat 已经指出的那样，您的分支因子为 2，最大深度为 2n，因此您看到的(非常非常)松散边界为 2 ²ⁿ = 4ⁿ 总节点，正如@KarolyHorvath 在评论中指出的那样，每个节点的工作将是线性的，因此给我们一个 O(n4ⁿ) 运行时间。