我将如何计算此递归函数的最坏情况时间复杂度？
How would I calculate the worst case time complexity of this recursive function?
我认为这根本没有效率。我正在尝试为此创建一个更快的实现（最好是二进制搜索或使用集合），但现在这就是我所在的位置。
我不确定它是否相关，但我创建了一个计数变量只是为了查看该方法被调用了多少次。来到了577次。
这是 "Subset Sum" 算法，我必须在其中显示添加到目标总和的所有子集，在本例中为 3165。
没有特别说明这个问题是算法，但我意识到这确实是同一个概念。
我的问题是我怎么知道这个程序的效率如何，方法调用指标吗？
public class SubsetSumAlgorithm {
static int count = 0;
public static void main(String[] args) {
int[] array = {26, 39, 104, 195, 403, 504, 793, 995, 1156, 1673};
System.out.println("COLLECTIONS IN ARRAY THAT ADD TO 3165: ");
findCollections(array, 0, 0, 3165, "");
System.out.println("Method called " + count + " times.");//method calls
}
public static void findCollections(int[] array, int index, int currentPosition, int sum, String collection) {
count++; //<---COUNTING THE METHOD CALLS HERE
if (array.length < index || currentPosition > sum) {
return;
}
//if sum is found, add to subset
for (int i = index; i < array.length; i++) {
if (currentPosition + array[i] == sum) {
System.out.println(collection + " " + array[i]);
}
//otherwise, call the method again
else if (currentPosition + array[i] < sum) {//recursive call
findCollections(array, i + 1, currentPosition + array[i], sum, collection + " " + array[i]);
}
}
}
}
这是输出：
COLLECTIONS IN ARRAY THAT ADD TO 3165:
26 195 793 995 1156
195 504 793 1673
Method called 577 times.
如果您想通过实验找到趋势，方法的调用次数是一个不错的指标。您需要使用不同的输入多次 运行 函数，收集数据，绘制图表并找到最佳拟合曲线...这将假设对 findCollections 的调用与其时间直接相关需要执行。
然而，在这里找到最坏的情况并不难。您只需要考虑哪些输入变量会导致您的执行时间最长。
在这种情况下，如果 sum 变量大于整个集合的总和，您将看到最差的执行（最多递归）。如果这个条件成立，那么下面的方法就等同于你的方法：
public static void findCollections(int[] array, int index, int currentPosition, int sum, String collection) {
for(int i = index; i < array.length; i++) {
findCollections(array, i + 1, currentPosition + array[i], sum, collection + " " + array[i]);
}
}
这里很容易看出，这将循环遍历 array 的所有可能子集。这使得您的解决方案 O(2^n) 其中 n 是 array
的大小
My question is how can I know how efficient this program is, and are the method calls an indicator?
推导算法渐近 运行 时间的唯一方法是亲自动手 手动 。话虽如此，当您的算法 运行s 不是 可靠的 或 合理的 方法时，尝试跟踪方法调用导出算法的运行时间。
要开始尝试弄清楚您的算法 运行s 有多快或多慢，我们可以从分析每行的 运行 时间推导循环开始：
1 public static void findCollections(int[] array, int index, int currentPosition, int sum, String collection) {
2 if(array.length < index || currentPosition > sum)
3 return;
4 for(int i = index; i < array.length; i++) {
5 if(currentPosition + array[i] == sum) {
6 System.out.println(collection + " " + array[i]);
7 }
8 else if(currentPosition + array[i] < sum) {
9 findCollections(array, i + 1, currentPosition + array[i], sum, collection + " " + array[i]);
10 }
11 }
12 }
...
1 -
2 1
3 1
4 n+1
5 n
6 n
7 -
8 n
9 n*T(n-1)
10 -
11 -
12 -
我们分析了每一行，我们可以推导出递归：
T(n) = n*T(n-1) + 4n + 3
=> T(n) = n*T(n-1) + 4n + Θ(1)
=> T(n) = n*T(n-1) + 4n
因为我们不能使用主定理，并且尝试使用递归树会很快变得非常混乱和混淆这个特定的递归，我们可以使用代入法来解决这个递归问题。我们将初始猜测设置为 2^n，因为在我看来它可能是指数级的：
上限O(2^n)
这意味着
T(n) ≤ c * 2^n
如果这个命题成立，这意味着我们也知道
T(n-1) ≤ c * 2^(n-1)
因此，我们现在可以写出我们的递归并尝试证明我们的猜测：
c * 2^n ≥ n * (c * 2^(n-1)) + 4n
=> c * 2^n ≥ c * n * 2^(n-1) + 4n
这适用于所有 n > 0 | c = 1，因此 T(n) = O(2^n)
下限Ω(2^n)
这意味着
T(n) ≥ c * 2^n
如果这个命题成立，这意味着我们也知道
T(n-1) ≥ c * 2^(n-1)
因此，我们现在可以写出我们的递归并尝试证明我们的猜测：
c * 2^n ≤ n * (c * 2^(n-1)) + 4n
=> c * 2^n ≤ c * n * 2^(n-1) + 4n
这适用于所有 n > 0 | c = 5000，因此 T(n) = Ω(2^n)
结论Θ(2^n)
由于我们已经证明该算法既是 O(2^n) 又是 Ω(2^n)，因此根据定义它也是 Θ(2^n) .所以基本上，你的算法的时间复杂度是 Θ(2^n) 这是 非常慢 因为它是指数级的。
我认为这根本没有效率。我正在尝试为此创建一个更快的实现（最好是二进制搜索或使用集合），但现在这就是我所在的位置。 我不确定它是否相关，但我创建了一个计数变量只是为了查看该方法被调用了多少次。来到了577次。
这是 "Subset Sum" 算法，我必须在其中显示添加到目标总和的所有子集，在本例中为 3165。 没有特别说明这个问题是算法，但我意识到这确实是同一个概念。
我的问题是我怎么知道这个程序的效率如何，方法调用指标吗？
public class SubsetSumAlgorithm {
static int count = 0;
public static void main(String[] args) {
int[] array = {26, 39, 104, 195, 403, 504, 793, 995, 1156, 1673};
System.out.println("COLLECTIONS IN ARRAY THAT ADD TO 3165: ");
findCollections(array, 0, 0, 3165, "");
System.out.println("Method called " + count + " times.");//method calls
}
public static void findCollections(int[] array, int index, int currentPosition, int sum, String collection) {
count++; //<---COUNTING THE METHOD CALLS HERE
if (array.length < index || currentPosition > sum) {
return;
}
//if sum is found, add to subset
for (int i = index; i < array.length; i++) {
if (currentPosition + array[i] == sum) {
System.out.println(collection + " " + array[i]);
}
//otherwise, call the method again
else if (currentPosition + array[i] < sum) {//recursive call
findCollections(array, i + 1, currentPosition + array[i], sum, collection + " " + array[i]);
}
}
}
}
这是输出：
COLLECTIONS IN ARRAY THAT ADD TO 3165:
26 195 793 995 1156
195 504 793 1673
Method called 577 times.
如果您想通过实验找到趋势，方法的调用次数是一个不错的指标。您需要使用不同的输入多次 运行 函数，收集数据，绘制图表并找到最佳拟合曲线...这将假设对 findCollections 的调用与其时间直接相关需要执行。
然而，在这里找到最坏的情况并不难。您只需要考虑哪些输入变量会导致您的执行时间最长。
在这种情况下，如果 sum 变量大于整个集合的总和，您将看到最差的执行（最多递归）。如果这个条件成立，那么下面的方法就等同于你的方法：
public static void findCollections(int[] array, int index, int currentPosition, int sum, String collection) {
for(int i = index; i < array.length; i++) {
findCollections(array, i + 1, currentPosition + array[i], sum, collection + " " + array[i]);
}
}
这里很容易看出，这将循环遍历 array 的所有可能子集。这使得您的解决方案 O(2^n) 其中 n 是 array
My question is how can I know how efficient this program is, and are the method calls an indicator?
推导算法渐近 运行 时间的唯一方法是亲自动手 手动 。话虽如此，当您的算法 运行s 不是 可靠的 或 合理的 方法时，尝试跟踪方法调用导出算法的运行时间。
要开始尝试弄清楚您的算法 运行s 有多快或多慢，我们可以从分析每行的 运行 时间推导循环开始：
1 public static void findCollections(int[] array, int index, int currentPosition, int sum, String collection) {
2 if(array.length < index || currentPosition > sum)
3 return;
4 for(int i = index; i < array.length; i++) {
5 if(currentPosition + array[i] == sum) {
6 System.out.println(collection + " " + array[i]);
7 }
8 else if(currentPosition + array[i] < sum) {
9 findCollections(array, i + 1, currentPosition + array[i], sum, collection + " " + array[i]);
10 }
11 }
12 }
...
1 -
2 1
3 1
4 n+1
5 n
6 n
7 -
8 n
9 n*T(n-1)
10 -
11 -
12 -
我们分析了每一行，我们可以推导出递归：
T(n) = n*T(n-1) + 4n + 3
=> T(n) = n*T(n-1) + 4n + Θ(1)
=> T(n) = n*T(n-1) + 4n
因为我们不能使用主定理，并且尝试使用递归树会很快变得非常混乱和混淆这个特定的递归，我们可以使用代入法来解决这个递归问题。我们将初始猜测设置为 2^n，因为在我看来它可能是指数级的：
上限O(2^n)
这意味着
T(n) ≤ c * 2^n
如果这个命题成立，这意味着我们也知道
T(n-1) ≤ c * 2^(n-1)
因此，我们现在可以写出我们的递归并尝试证明我们的猜测：
c * 2^n ≥ n * (c * 2^(n-1)) + 4n
=> c * 2^n ≥ c * n * 2^(n-1) + 4n
这适用于所有 n > 0 | c = 1，因此 T(n) = O(2^n)
下限Ω(2^n)
这意味着
T(n) ≥ c * 2^n
如果这个命题成立，这意味着我们也知道
T(n-1) ≥ c * 2^(n-1)
因此，我们现在可以写出我们的递归并尝试证明我们的猜测：
c * 2^n ≤ n * (c * 2^(n-1)) + 4n
=> c * 2^n ≤ c * n * 2^(n-1) + 4n
这适用于所有 n > 0 | c = 5000，因此 T(n) = Ω(2^n)
结论Θ(2^n)
由于我们已经证明该算法既是 O(2^n) 又是 Ω(2^n)，因此根据定义它也是 Θ(2^n) .所以基本上，你的算法的时间复杂度是 Θ(2^n) 这是 非常慢 因为它是指数级的。