Recursive递归的时间空间复杂度计算

基本概念

递归可以层次可以通过tree的形式展现。

比如下面的递归：

int f(int n) {
  if (n <= 1) {
    return 1;
  }
  return f(n - 1) + f(n - 1);
} 

时间复杂度:
就是总的树的节点s数。如果每一次层嵌套都包涵2层平行的call，那时间复杂度就是O(2^N).如果有四层，那么就是O（4^N).

空间复杂度:
就是总的树的深度。在这里就是N

深度优先算法(DFS: Depth First Search)

深度优先算法是一个递归调用。对于图的深度优先，我们有Vertices和Edge的数量，分别用V和E来表示。

时间复杂度：
因为是图，所以在递归的时候每一次层有多少节点是不知道的，所以没办法按照2^n的普遍算法来算。但是换一个思路就是无论如何每条边都至少需要走一遍。
时间复杂度就是总的边的数量，每条边会被访问两次，一次是遍历，一次是会退。O(E).

空间复杂:
如果所有的Vertices都是相连的，那么就会有V层深度的书。那空间复杂度就是O(V)

广度优先算法(BFS: Breadth First Search)

todo

时间复杂度:

O(V+E). 这里不是说O(E)比O（V+E）好。其实O(E)是O(2E).因为复杂度计算忽略常量，这里容易引起误解。

空间复杂:

O(V)

Reference:

https://stackoverflow.com/questions/43298938/space-complexity-of-recursive-function
https://zhuanlan.zhihu.com/p/95081559#:~:text=%E5%9C%A8%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95,%E5%BA%A6%E4%B8%BAO(V)%E3%80%82