我如何找到这个递归算法的复杂性?用二进制数替换字符串中的模式

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).