时间戳

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

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

问题描述

该算法本质上是在给定的二进制字符串中找到星号 (*)，并将其替换为 0 和 1，以输出二进制字符串的所有不同组合。

我最初认为这个算法是 O(2^n)，但是，在我看来，它只考虑了字符串中的星数 (*)。字符串的长度呢？因为如果给定字符串中没有星号，它在技术上应该仍然是线性的，因为递归调用的数量取决于字符串长度，但我原来的 O(2^n) 似乎没有考虑到这一点，因为它会变成O(1) 如果 n = 0。

我应该如何找出它的时间和空间复杂度？谢谢。

代码：

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 是字符串的长度。

标签： algorithmrecursiontime-complexitycomplexity-theorybacktracking

解决方案

Big-O 表示法的想法是给出一个上限的估计，即如果算法的阶数是 O(N^4) 运行时，它仅仅意味着算法不能做得比这更糟。

可以说，可能有一个 O(N) 运行时的算法，但我们仍然可以说它是 O(N^2)。因为 O(N) 永远不会比 O(N^2) 更糟。但是在计算意义上，我们希望估计值尽可能接近和严格，因为它可以让我们更好地了解算法的实际执行情况。

在您当前的示例中， O(2^N) 和 O(2^L), N 是字符串的长度，L 是 * 的数量，都是有效的 upperbounds。但是由于 O(2^L) 对算法及其对 * 字符的存在的依赖性给出了更好的了解，因此 O(2^L) 是算法的更好和更严格的估计（因为 L<=N）。

更新：空间复杂度取决于实现。在您当前的实现中，假设 StringBuilder 是通过引用传递的，并且在每个递归调用中都没有创建字符串的副本，那么空间复杂度确实是 O(N)，即递归调用堆栈的大小。如果是传值，每次调用前都拷贝到栈中，那么整体复杂度就是O(N * N)，即(O(max_number_of_recursive_calls * size_of_string))，因为拷贝操作的代价是O(size_of_string) .

推荐阅读