c++ - 这个递归函数的时间复杂度是多少？

Question

void solve(string op, int n, int zeros, int ones)
{
    if(n==0){
        cout<<op<<" ";
        return;
    }
    string op1 = op;
    op1.push_back('1');
    solve(op1, n-1, zeros, ones+1);
    if(ones > zeros){
        string op2 = op;
        op2.push_back('0');
        solve(op2, n-1, zeros+1, ones);
        return;
    }

}

求解函数的时间复杂度是多少？是 O(2^N) 吗？有人可以解释一下您如何找到递归函数的复杂性吗？

问题链接:https://www.geeksforgeeks.org/print-n-bit-binary-numbers-1s-0s-prefixes/

Answer 1

所以，我们想在这里估计最坏的情况。最坏的情况是条件 (ones > zeros) 总是返回 true。可能吗？是的，如果 ones-zeros >= n。由于我不知道您的任务的上下文，我可能会假设它。

设 T(n) 是函数的复杂度。您的函数用 (n-1) 调用自身两次。也就是说，

T(n) = T(n-1) + T(n-1) + c

其中 c 是您正在执行的例程的常量，例如附加“1”或“0”、条件评估等。不依赖于 n。

所以，

T(n) = 2T(n-1) + c =
     = 2(2T(n-2) + c) + c = 4T(n-2) + 3c = 
     = 4(2T(n-3) + c) + 3c = 8T(n-3) + 7c = 
     = ...
     = 2^k*T(n-k) + (2^k-1)*c

所以如果 (n-k) == 0，你就完成了，因为 T(0) = z。所以，当 k == n 时我们就完成了。关于 z 并不明显。在当前的实现中，我们确实输出了一个 O(n) 的字符串。如果我们只对字符串进行计数，它将是 O(1)。如果我们打印是必不可少的，那么最终的复杂度将是 O(n2^n) 如果不是那么 O(2^n)

也就是说，

T(n) = z*2^n + (2^n - 1)*c = O(z2^n)

[更新1]

在意识到从代码片段中不清楚但在阅读提供的链接中的信息后变得清晰的真正问题之后，我会说复杂性是不同的。

以上计算在假设条件下仍然成立。

现在，对于这个问题。我们想找到所有长度为 n 的 1 和 0 序列，其中每个前缀包含的 1 不少于该前缀中 0 的数量。

算法提供了这个问题的解决方案。正如您在每次递归调用中注意到的那样，算法将 0 或 1 添加到结果序列中。这意味着递归调用的次数恰好是结果字符串中符号的数量。

我们知道每个结果字符串的长度是n。所以，我们需要计算出字符串的数量。让我们看看您的程序针对不同的 n 找到了什么:

n    | number of strings 
-----------------------
1    |    1
2    |    2
3    |    3
4    |    6
5    |    10
6    |    20
7    |    35
8    |    70

因此，如果仔细观察，您会发现这些是二项式系数 C(n, n/2)。这个二项式系数可以通过大n估计为~2^n/(\pi * n/2)。因此，算法的复杂度为 O(2^n/(n))。但是，如果我们还考虑在递归结束时打印，我们需要乘以 n，因为它是输出字符串的长度。所以，我们最终得到 O(2^n)

为了干净，我们需要证明我们的假设是正确的。希望你能通过归纳法或其他方法做到这一点。

[更新2]

您的实现在每次迭代时都会处理字符串。这会减慢 n 倍的执行速度。您可以通过传递对字符串的引用并在递归调用后删除添加的字符来避免它，如下所示:

void solve(string &op, int n, int zeros, int ones)
{
    if(n==0){
        cout<<op<<" ";
        return;
    }
    op.push_back('1');
    solve(op, n-1, zeros, ones+1);
    op.pop_back();
    if(ones > zeros){
        op.push_back('0');
        solve(op, n-1, zeros+1, ones);
        op.pop_back();
        return;
    }    
}