计算其中具有循环的递归函数的时间复杂度

Question

我当时正在研究一个简单的问题，后来想出了C ++中的递归函数，以下是我的函数。

void test(int arr[],int n,int x = 0){
    cout<<arr[x];
    for(int i = x+1;i < n;i++){
        test(arr, n, i);
    }
}

我想知道，如果有人可以计算上述方法的时间复杂度，那么上述函数的时间复杂度将是多少，这将对改善我的功能有很大帮助。

Answer 1

您可以像下面这样编写其经常性关系：

 T(n) = T(n-1) + T(n-2) + ... + T(1) + 1

确实T'(x)是T(n - x)和T(1) = 1（该位置中的最后一个是cout）。我们可以看到：

T(2) = T(1) + 1 = 2
T(3) = T(2) + T(1) + 1 = 2 + 1 + 1 = 4
T(4) = 4 + 2 + 1 + 1 = 2^2 + 2^1 + 2^0 + 1 = 8
T(5) = 8 + 4 + 2 + 1 + 1 = 2^3 + 2^2 + 2^1 + 2^0 + 1 = 16
.
.
.
T(n) = 2^{n-2} + 2^{n-1} + ... + 2^0 + 1 = 2^{n-1}

因此，T(n) = \Theta(2^n)。