我如何找到这个递归算法的复杂性?用二进制数替换字符串中的模式
How do I find the complexity of this recursive algorithm? Replace pattern in string with binary number
该算法本质上是在给定的二进制字符串中找到星号 (*),并用 0 和 1 替换它以输出二进制字符串的所有不同组合。
我本来以为这个算法是O(2^n),然而,在我看来,这只考虑了字符串中的星数(*)。字符串的长度如何?因为如果给定的字符串中没有星星,它在技术上应该仍然是线性的,因为递归调用的数量取决于字符串长度,但我原来的 O(2^n) 似乎没有考虑到这一点,因为它会变成O(1) 如果 n = 0.
我应该如何找出它的时间和 space 复杂度?谢谢
代码:
static void RevealStr(StringBuilder str, int i) {
//base case: prints each possibility when reached
if(str.length() == i) {
System.out.println(str);
return;
}
//recursive step if wild card (*) found
if(str.charAt(i) == '*') {
//exploring permutations for 0 and 1 in the stack frame
for(char ch = '0'; ch <= '1'; ch++) {
//making the change to our string
str.setCharAt(i, ch);
//recur to reach permutations
RevealStr(str, i+1);
//undo changes to backtrack
str.setCharAt(i, '*');
}
return;
}
else
//if no wild card found, recur next char
RevealStr(str, i+1);
}
编辑:我目前正在考虑 O(2^s + l),其中 s 是星星的数量,l 是字符串的长度。
要解决这个问题,我们可以做一个手册 运行:
基数: n=1
RevealStr("*", 1)
满足第一个if的条件,我们只运行这一次输出*
下一个: n=2
RevealStr("**", 1)
RevealStr("0*", 2)
RevealStr("00", 2)
RevealStr("01", 2)
RevealStr("1*", 2)
RevealStr("10", 2)
RevealStr("11", 2)
下一个:n=3
RevealStr("***", 1)
RevealStr("0**", 2)
RevealStr("00*", 2)
RevealStr("000", 3)
RevealStr("001", 3)
RevealStr("01*", 2)
RevealStr("010", 3)
RevealStr("011", 3)
RevealStr("1**", 2)
RevealStr("10*", 2)
RevealStr("100", 3)
RevealStr("101", 3)
RevealStr("11*", 2)
RevealStr("110", 3)
RevealStr("111", 3)
你可以看到当 n=2 时,RevealStr
被调用了 7 次,而当 n=3 时它被调用了 15 次。这遵循函数 F(n)=2^(n+1)-1
对于最坏的情况,复杂度似乎是 O(2^n),即 n 颗星星的数量
Big-O 符号的想法是给出一个上限的估计,即如果算法的顺序是 O(N^4) 运行时它只是意味着算法不能做任何 比那更糟。
比方说,可能有一个 O(N) 阶运行时间的算法,但我们仍然可以说它是 O(N^2)。因为 O(N) 永远不会比 O(N^2) 差。但是在计算意义上,我们希望估计尽可能接近和严格,因为它会让我们更好地了解算法的实际执行情况。
在您当前的示例中,O(2^N) 和 O(2^L),N 是字符串的长度,L 是 * 的数量,都是有效上限 .但是由于 O(2^L) 给出了关于算法的更好的想法及其对 * 字符存在的依赖性,O(2^L) 是算法的更好和更严格的估计(因为 L<=N)。
更新: space 复杂性取决于实现。在您当前的实现中,假设 StringBuilder 是通过引用传递的,并且在每个递归调用中都没有创建字符串副本,space 复杂度确实是 O(N),即递归调用堆栈的大小。如果它是按值传递的,并且每次调用之前都将其复制到堆栈,则整体复杂度将为 O(N * N),即 (O(max_number_of_recursive_calls * size_of_string)),因为复制操作成本为 O(size_of_string).
该算法本质上是在给定的二进制字符串中找到星号 (*),并用 0 和 1 替换它以输出二进制字符串的所有不同组合。
我本来以为这个算法是O(2^n),然而,在我看来,这只考虑了字符串中的星数(*)。字符串的长度如何?因为如果给定的字符串中没有星星,它在技术上应该仍然是线性的,因为递归调用的数量取决于字符串长度,但我原来的 O(2^n) 似乎没有考虑到这一点,因为它会变成O(1) 如果 n = 0.
我应该如何找出它的时间和 space 复杂度?谢谢
代码:
static void RevealStr(StringBuilder str, int i) {
//base case: prints each possibility when reached
if(str.length() == i) {
System.out.println(str);
return;
}
//recursive step if wild card (*) found
if(str.charAt(i) == '*') {
//exploring permutations for 0 and 1 in the stack frame
for(char ch = '0'; ch <= '1'; ch++) {
//making the change to our string
str.setCharAt(i, ch);
//recur to reach permutations
RevealStr(str, i+1);
//undo changes to backtrack
str.setCharAt(i, '*');
}
return;
}
else
//if no wild card found, recur next char
RevealStr(str, i+1);
}
编辑:我目前正在考虑 O(2^s + l),其中 s 是星星的数量,l 是字符串的长度。
要解决这个问题,我们可以做一个手册 运行:
基数: n=1
RevealStr("*", 1)
满足第一个if的条件,我们只运行这一次输出*
下一个: n=2
RevealStr("**", 1)
RevealStr("0*", 2)
RevealStr("00", 2)
RevealStr("01", 2)
RevealStr("1*", 2)
RevealStr("10", 2)
RevealStr("11", 2)
下一个:n=3
RevealStr("***", 1)
RevealStr("0**", 2)
RevealStr("00*", 2)
RevealStr("000", 3)
RevealStr("001", 3)
RevealStr("01*", 2)
RevealStr("010", 3)
RevealStr("011", 3)
RevealStr("1**", 2)
RevealStr("10*", 2)
RevealStr("100", 3)
RevealStr("101", 3)
RevealStr("11*", 2)
RevealStr("110", 3)
RevealStr("111", 3)
你可以看到当 n=2 时,RevealStr
被调用了 7 次,而当 n=3 时它被调用了 15 次。这遵循函数 F(n)=2^(n+1)-1
对于最坏的情况,复杂度似乎是 O(2^n),即 n 颗星星的数量
Big-O 符号的想法是给出一个上限的估计,即如果算法的顺序是 O(N^4) 运行时它只是意味着算法不能做任何 比那更糟。
比方说,可能有一个 O(N) 阶运行时间的算法,但我们仍然可以说它是 O(N^2)。因为 O(N) 永远不会比 O(N^2) 差。但是在计算意义上,我们希望估计尽可能接近和严格,因为它会让我们更好地了解算法的实际执行情况。
在您当前的示例中,O(2^N) 和 O(2^L),N 是字符串的长度,L 是 * 的数量,都是有效上限 .但是由于 O(2^L) 给出了关于算法的更好的想法及其对 * 字符存在的依赖性,O(2^L) 是算法的更好和更严格的估计(因为 L<=N)。
更新: space 复杂性取决于实现。在您当前的实现中,假设 StringBuilder 是通过引用传递的,并且在每个递归调用中都没有创建字符串副本,space 复杂度确实是 O(N),即递归调用堆栈的大小。如果它是按值传递的,并且每次调用之前都将其复制到堆栈,则整体复杂度将为 O(N * N),即 (O(max_number_of_recursive_calls * size_of_string)),因为复制操作成本为 O(size_of_string).