recursion递归的时间复杂度

The time complexity of a recursive function depends on the number of times the function is called and the time complexity of a single call.

  1. void f(int n) {
  2.     if (n == 1) return;
  3.     f(n-1);
  4. }
  6. //The call f(n) causes n function calls, 
  7. //and the time complexity of each call is O(1).
  8. //Thus, the total time complexity is O(n).

再看下面这一个

  1. void g(int n) {
  2.     if (n == 1) return;
  3.     g(n-1);
  4.     g(n-1);
  5. }
  7. //g(n)   调用1次
  8. //g(n-1) 调用2次
  9. //g(n-2) 调用4次
  11. //1+2+4+ ... + 2^(n-1) = 2^n-1 = O(2^n)

在算法竞赛当中，会给出时间限制和空间限制，一般时间限制是1s，此时不能超过1e8
这个值是跑出来的经验值，取决于评测机环境，CCF官方评测机跑出来的，不能超过1e8，1e8也是危险的