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

Question

该算法本质上是在给定的二进制字符串中找到星号 (*)，并用 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 是字符串的长度。

Answer 1

要解决这个问题，我们可以做一个手册运行:

基数： 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 颗星星的数量

Answer 2

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

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

How do I find the complexity of this recursive algorithm? Replace pattern in string with binary number

algorithm

recursion

time-complexity

complexity-theory

backtracking