preface：休假一周去了苏州散心，发现苏州人真的很重视英语，看了不少于前0个家庭都在教孩子英语了。深感内地教育落后于他们，如果再不学习，会落后的更厉害，加上现在国际国内形势如此严峻，所谓的铁饭碗将来可能将不复存在，所以学好一门技能还是非常有必要的，所以我决心把leetcode继续刷起来。这篇笔记只会记录本人刷题的一些心得体会或者有用的八股。fighting！！！

1、时间复杂度和空间复杂度

普通的时间复杂度和空间复杂度没什么好讲的，算就行了。重要的是递归的空间复杂度和时间的复杂度。

1.1递归程序的时间复杂度

递归算法的时间复杂度本质上要看：递归的次数 $\times$ 每次递归的时间负责度。

a、拿斐波那契数列求和的程序来看：

int fibonacci(int i){if(i < 0) return 0;else if(i == 1) return 1;else return fibonacci(i - 1) + fibonacci(i - 2);
}

对于这个递归算法，每次递归的过程都是$O(1)$的操作，而对于这份递归算法如果画出他的递归图，就是一颗二叉树，二叉树的每个节点都是一次递归，根据一颗深度为k的二叉树最多可以有$2^k-1$个节点可知，该递归算法的时间复杂度为$O(2^n)$。

b、拿递归二分查找来看

int binary_search( int arr[], int l, int r, int x) {if (r >= l) {int mid = l + (r - l) / 2;if (arr[mid] == x)return mid;if (arr[mid] > x)return binary_search(arr, l, mid - 1, x);return binary_search(arr, mid + 1, r, x);}return -1;

根据二分查找的思路（将排序的数组不停的折，最终折到要找的数，假设要折n次，则有$2^n=target$）可以知道二分查找的时间复杂度是 $O(logn)$。

1.2递归程序的空间复杂度

递归算法的空间复杂度本质上要看：递归深度（即递归多少次） $\times$ 每次递归的空间复杂度。
递归在操作系统层面就是不停的入栈出栈的过程，每次递归就是将所需的空间压到栈中，递归结束后再把递归的数据弹出去。所以这个栈的深度就是递归的深度。
对于斐波那契数列，递归调用的深度就是 n, 每次递归调用的空间复杂度为$O(1)$（因为无需开辟新空间）。

对于递归的二分查找算法，递归调用的深度就是要折的次数，即$logn$，如果二分查找传参的时候传的是数组的首地址，则每次递归的空间复杂度为$O(1)$，此时二分查找的空间复杂度为$O(logn)$；如果传的是整个数组，则每次递归的空间复杂度为$O(n)$，此时二分查找的空间复杂度为$O(nlogn)$。

2、数组

i will fill it soon…

3、排序

i will fill it soon…

4、字符串

i will fill it soon…