具有多重递归的 java 方法的成本

Question

我们有以下Java方法：

static void comb(int[] a, int i, int max) {
    if(i < 0) {
        for(int h = 0; h < a.length; h++)
            System.out.print((char)(’a’+a[h]));
        System.out.print("\n");
        return;
    }
    for(int v = max; v >= i; v--) {
        a[i] = v;
        comb(a, i-1, v-1);
    }
}

static void comb(int[] a, int n) { // a.length <= n
    comb(a, a.length-1, n - 1);
    return;
}

我必须根据输入的大小确定算法成本的渐近估计 comb(int[],int)。因为我刚开始做这种类型的练习，所以我不明白在这种情况下输入大小是指数组的大小 a 还是其他一些方法参数。一旦确定了输入大小，如何继续确定具有多重递归的成本？

拜托，你能告诉我决定成本的递归方程吗？

Answer 1

基本上对于给定大小的输入数组，计算答案需要多少步？如果将输入大小加倍，步数会发生什么变化？关键是检查你的循环并计算出它们执行了多少次。

Answer 2

原来被调用的方法是comb(int[] a, int n)，你知道是a.length <= n。这意味着您可以使用 n 的函数来绑定方法的运行时间，但是您应该考虑是否可以使用 n 和 [=14] 的函数来计算更好的绑定=].

例如，如果该方法执行 a.length * n 个步骤并且每个步骤花费固定的时间，您可以说该方法花费 O(n^2) 时间，但 O(a.length * n) 将是更准确（特别是如果 n 比 a.length 大很多。

你应该分析递归调用了多少次方法，每次调用有多少操作。

Answer 3

要确定此算法的复杂性，您必须了解 "work" 您花费最多的时间。不同类型的算法可能取决于其参数的不同方面，如输入大小、输入类型、输入顺序等。这取决于数组大小和 n.

像 System.out.print, (char), 'a' + a [h], a.length, h++ 等操作是恒定时间操作，主要取决于编译后您将获得的处理器命令以及您将在其上执行这些指令的处理器。但最终它们可以总结为常量C。该常量不依赖于算法和输入大小，因此您可以放心地将其从估计中忽略。

该算法线性依赖于输入大小，因为它是循环的，它是输入数组（从 h = 0 到最后一个数组元素有一个循环）。并且因为 n 可以等于数组大小（a.length = n - 这是该算法的最坏情况，因为它强制执行递归 "array size" 次）我们应该在我们的估计中考虑这种输入情况.然后我们得到另一个递归循环，它将执行方法 comb 其他 n 次。

因此，在最坏的情况下，对于非常大的输入大小常数，我们将获得 O(n*n*C) 的执行步骤数 C 将变得微不足道，因此您可以将其从估计中省略。因此最终估计将是 O(n^2).

具有多重递归的 java 方法的成本

Cost of a java method with multiple recursion

java

algorithm

recursion

recurrence

asymptotic-complexity