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

本文介绍了计算其中具有循环的递归函数的时间复杂度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在研究一个简单的问题，我想出了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）。