时间复杂度和空间复杂度
时间复杂度：算法需要执行的运算次数。而不是计算程序需要的时间。
定义
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
如何计算时间复杂度
1.先计算基本操作重复执行的次数T(n)。
2.寻找T(n)同数量级f(n),同数量级一般有以下：1，logn，n，nlogn ，n的平方，n的三次方，2的n次方，n!。
3.计算T(n)/f(n)求极限看是否为常数c，如果存在常数c，则时间复杂度为O(f(n))。
二分法的时间复杂度即推理过程
假设使用二分法从一个长度为N的序列中查找一个元素。
推理过程：
| 查找次数 | 待查询的元素数量 |
|---|---|
| 1 | N/2 |
| 2 | N/2^2 |
| 3 | N/2^3 |
| k | N/2^k |
我们知道:N/2^k>=1,而且计算时间复杂度都是按最坏的情况计算，因此
N/2^k = 1 =>
2^k = N =>
k=log2N
所以二分法查找重复执行的次数T(n)为log2N.
根据时间复杂度的定义，存在常数c，使得T(n)/f(n)。这里我们假设f(n)=logN，
则c=log2N/logN=1/2，满足条件。所以二分法的时间复杂度为O(logN)。
时间复杂度中的log（n）底数到底是多少？
所以，这里的推导过程是对的，但是时间复杂度为不对，不应该是log2N，而应该是logN。
举例：算法执行次数为：T(n) = n^2，那么 f(n) = n^2， f(n) = n^3， f(n) = n^4都是成立的，但是因为第一个 f(n)/T(n) =1，其他都为0，不符合条件，所以我们说这个算法的复杂度是 O(n^2) 。
常见时间复杂度
1.常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)；如果 T(n) 不等于一个常数项时，直接将常数项省略。
int aFunc(void) {
printf("Hello, World!\n"); // 需要执行 1 次
return 0; // 需要执行 1 次
}
T(n) = 2,它的时间复杂度就是：O(1)。
如果T(n) = n + 29,因为常数项可以省略，所以，它的时间复杂度为：O(n)。
2.对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c...，则这个循环的时间复杂度为 O(n×a×b×c...)。分析的时候应该由里向外分析这些循环。
void aFunc(int n) {
for(int i = 0; i < n; i++) { // 循环次数为 n
for(int j = 0; j < n; j++) { // 循环次数为 n
printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
}
}
}
此时时间复杂度为 O(n × n × 1)，即 O(n^2)。
3.对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。
void aFunc(int n) {
// 第一部分时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf("Hello, World!\n");
}
}
// 第二部分时间复杂度为 O(n)
for(int j = 0; j < n; j++) {
printf("Hello, World!\n");
}
}
此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。
4.对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。
void aFunc(int n) {
if (n >= 0) {
// 第一条路径时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf("输入数据大于等于零\n");
}
}
} else {
// 第二条路径时间复杂度为 O(n)
for(int j = 0; j < n; j++) {
printf("输入数据小于零\n");
}
}
}
此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。
例子：
1.斐波那契数列实现一（递归算法）
long aFunc(int n) {
if (n <= 1) {
return 1;
} else {
return aFunc(n - 1) + aFunc(n - 2);
}
}
显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。
显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列，通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。
所以该方法的时间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)。
空间复杂度：O(n)。
2.斐波那契数列实现二（迭代算法）
//斐波那契数列:[1,1,2,3,5,8,13,21,34,55]
int FeibonacciInteraction(int a, int b, int num) {
int c = 0;
if (num <=0 ) {
return -1;
}else if (num == 1) {
return a;
}else if (num == 2) {
return b;
}else{
while (num -2) {
c = a + b;
a = b;
b = c;
num --;
}
return c;
}
}
它的时间复杂度为：O(n)。
空间复杂度：O(1)。
4.二分法（迭代方法）
int BinarySearch(int arr[], int len, int num) {
assert(arr);
//arr:[1,2,3,4,5,6,7,8,9]
int left = 0;
int right = len - 1;
int mid;
while (left <= right) {
//0 + 8 + 1 = 9
//
mid = left + (right - left) / 2;
if (num > arr[mid]) {
left = mid + 1;
}else if (num < arr[mid]) {
right = mid - 1;
}else{
return mid;
}
}
return -1;
}
每次都是在原有内容进行二分，所以时间复杂度是O(logn)。
因为变量值创建一次，所以空间复杂度为O(1)。
5.二分法（递归）
int BinarySearchRecursion(int arr[5], int left, int right, int aim) {
int mid = left + (right - left) / 2;
if (left <= right) {
if (aim < arr[mid]) {
right = mid - 1;
BinarySearchRecursion(arr, left, right, aim);
}else if(arr[mid] < aim){
left = mid + 1;
BinarySearchRecursion(arr, left, right, aim);
}else if (aim == arr[mid]) {
return mid;
}
}
return -1;
}
时间复杂度为：O(logn)。
每进行一次递归都会创建变量，所以空间复杂度为O(logn)。
6.进阶：
void aFunc(int n) {
for (int i = 2; i < n; i++) {
i *= 2;
printf("%i\n", i);
}
}
假设循环次数为 t，则循环条件满足 2^t < n。
可以得出，执行次数t = log(2)(n)，即 T(n) = log(2)(n)，可见时间复杂度为 O(log(2)(n))，即 O(log n)。这个不懂？？？？
空间复杂度
空间复杂度 ：对一个算法在运行过程中临时占用存储空间大小的量度。
计算方法
①忽略常数，用O(1)表示
②递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
③对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。
例子
int a;
int b;
int c;
printf("%d %d %d \n",a,b,c);
它的空间复杂度O（n）=O（1）；
2.递归
int fun(int n,)
{
int k=10;
if（n==k)
return n;
else
return fun(++n);
}
递归实现，调用fun函数，每次都创建1个变量k。调用n次，空间复杂度O（n*1）=O（n)。
参考链接：
十分钟搞定时间复杂度
时间复杂度和空间复杂度的简单讲解
