## 递归函数的时间复杂度计算 递归的时间复杂度由递归调用次数和函数本身所用时间决定。 ```c++ void A(int x){ if(x){ A(x / 2); } } A(n); //每次递归调用时参数都会减半，到0时停止递归。总共调用函数log n次，总时间复杂度为O(log n)。 ``` ```c++ void A(int x){ if(x){ A(x - 1); } } A(n); //每次递归调用时参数都会减1，到0时停止递归。总共调用函数n次，总时间复杂度为O(n)。 ``` ```c++ // 以递归求解斐波拉契举例 int F(int n){ if (n <= 2) { return 1; } return F(n - 1) + F(n - 2); } cout << F(n); /* 函数中有2次递归调用。 第1层有1个参数为n的调用。 第2层有1个参数为n - 1的调用,1个参数为n - 2的调用。 第3层有1个参数为n - 2的调用,2个参数为n - 3的调用,1个参数为n - 4的调用。 …… 总共有n + 1层调用。 总时间复杂度为O(2^n)。 */ ``` ```c++ void A(int x){ if(x){ A(x / 2); A(x / 2); } } A(n); /* 函数中有2次递归调用。 第1层有1个参数为n的调用。 第2层有2个参数为n / 2的调用。 第3层有4个参数为n / 4的调用。 …… 总共有log n层调用。 总时间复杂度为O(n)。 */ ``` ```cpp void A(int x) { for (int i = 1; i <= x; i++) { } if (x) { A(x / 2); A(x / 2); } } A(n); ``` ```c++ void A(int x){ for(int i = 1; i <= x; ++i){ A(x - 1); } } A(n); /* 递归函数中有x次递归调用。 第1层有1个参数为n的调用。 第2层有n个参数为n - 1的调用。 第3层有n(n - 1)个参数为n - 2的调用。 …… 总共有n + 1层调用。 总时间复杂度为O(n!)。 */ ``` ## 递归的空间复杂度计算 递归的空间复杂度由正在调用的递归函数数量和函数本身所占空间决定。 ```c++ void A(int x){ if(x){ A(x - 1); } } A(n); // 函数的空间复杂度为O(1)。递归调用的层数为n。空间复杂度为O(n)。 ``` ```c++ void A(int x){ if(x){ A(x / 2); A(x / 2); } } A(n); // 函数的空间复杂度为O(1)。递归调用的层数为log n。总空间复杂度为O(log n)。 ``` ```cpp void A(int x) { vector<int> a(x); if (x) { A(x / 2); A(x / 2); } } A(n); ```