计算其中具有循环的递归函数的时间复杂度 [英] Calculating time complexity of a recursive function having a loop inside it

问题描述

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

I was working on a simple problem and I came up with a recursive function in C++, below is my function.

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

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

I wonder what will be the time complexity of the above function if anyone can calculate the time complexity for the above method it will be a great help in improving my function.

推荐答案

写它的递归关系如下：

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

实际上是 T'（ x）是 T（n-x）和 T（1）= 1 （实际情况中的最后一个是针对 cout ）。我们可以看到：

Indeed T'(x) is T(n - x) and T(1) = 1 (The last one in the realtion is is for cout). We can see:

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）。

这篇关于计算其中具有循环的递归函数的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！