具有两个递归调用的递归算法的时间复杂度 [英] Time complexity of recursive algorithm with two recursive calls

问题描述

我正在尝试分析可解决

I am trying to analyze the Time Complexity of a recursive algorithm that solves the Generate all sequences of bits within Hamming distance t problem. The algorithm is this:

// str is the bitstring, i the current length, and changesLeft the
// desired Hamming distance (see linked question for more)
void magic(char* str, int i, int changesLeft) {
        if (changesLeft == 0) {
                // assume that this is constant
                printf("%s\n", str);
                return;
        }
        if (i < 0) return;
        // flip current bit
        str[i] = str[i] == '0' ? '1' : '0';
        magic(str, i-1, changesLeft-1);
        // or don't flip it (flip it again to undo)
        str[i] = str[i] == '0' ? '1' : '0';
        magic(str, i-1, changesLeft);
}

此算法的时间复杂度是多少?

What is the time complexity of this algorithm?

我对此感到非常生锈，这是我的尝试，我觉得这与事实不符:

I fond myself pretty rusty when it comes to this and here is my attempt, which I feel is no where near the truth:

t(0) = 1
t(n) = 2t(n - 1) + c
t(n) = t(n - 1) + c
     = t(n - 2) + c + c
     = ...
     = (n - 1) * c + 1
    ~= O(n)

其中n是位字符串的长度.

where n is the length of the bit string.

相关问题: 1 ，2 .

推荐答案

它是指数:

t(0) = 1
t(n) = 2 t(n - 1) + c
t(n) = 2 (2 t(n - 2) + c) + c          = 4 t (n - 2) + 3 c
     = 2 (2 (2 t(n - 3) + c) + c) + c  = 8 t (n - 3) + 7 c
     = ...
     = 2^i t(n-i) + (2^i - 1) c         [at any step i]
     = ...
     = 2^n t(0) + (2^n - 1) c          = 2^n + (2^n - 1) c
    ~= O(2^n)

或者使用WolframAlpha: https://www.wolframalpha.com/input/?i=t(0)％3D1，+ t(n)％3D2 + t(n-1)+％ 2B + c

Or, using WolframAlpha: https://www.wolframalpha.com/input/?i=t(0)%3D1,+t(n)%3D2+t(n-1)+%2B+c

它是指数级的原因是您的递归调用将问题大小减小了1，但是您要进行两个递归调用.您的递归调用正在形成二叉树.

The reason it's exponential is that your recursive calls are reducing the problem size by 1, but you're making two recursive calls. Your recursive calls are forming a binary tree.

这篇关于具有两个递归调用的递归算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！