一：算法效率-时间和空间复杂度

    完成某个功能可能有多种实现的算法，可是如何去评判算法的好坏呢。最为直观的就是判断某个算法时间复杂度，正如用速度描述物体运行的快慢一样，我们可以用时间复杂度来评判某个算法的快慢或好坏。而对于空间复杂度来说，在如今现代计算机的发展，我们已经无需过多考虑空间复杂度，首当其冲最为关心的还是算法是否够快，也就是时间复杂度。

二：时间复杂度

（1）时间复杂度的概念

    时间复杂度究其本质而言就是运行一个算法的具体时间，但是这里有一个具体的问题：就是我们不可能眼瞅着算法就把它的运行时间给说出来，更何况一个算法的运行实践不止跟算法本身的实现方法有关，而且还跟其运行的环境相关，所以这样说的话如果用所谓的时间去表示时间复杂度的话，那么横向上来看，不同算法的时间复杂度就无法比较了。所以时间复杂度是指算法中的基本操作的执行次数。

（2）大O的渐进表示法

A：例子

且看如下代码，请计算它的执行次数

void Fun1(int N)
{int count = 0;for (int i = 0; i < N; i++)//总共N次{for (int j = 0; j < N; j++){count++;}}
}
for (int k = 0; k < 2 * N; ++k)//总共2N次
{count++;
}
int M = 10;while (M--)//总共10次
{count++;
}
printf("%d\n", count);

可以很容易计算出的它的执行次数为N²+2*N+10
用函数表示为F(N)=N²+2*N+10

B：大O的渐进表示法

上面的函数中如果N取值很小，那么整个的结果会和一次项和常数项有关，但是随着N变得很大，最终的结果似乎只取决于二次项了。这和咋们在高数极限计算中的“取大头”思想有点像
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
推导大O阶方法如下

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶（也就是说N²和2N²是一样的）

于是经过推导，上述例子中的算法时间复杂度为O(N²)

（3）最好最坏情况

有些算法是由“概率“的，也就是不确定性。比如顺序查找，其在查找过程中有可能第一次找见，也有可能第二次找见，还有可能第N次找见。如果是第一次找见那么就是这个算法的最好情况，如果是第N次找见那么就是它的最坏情况，这样一般情况（平均情况）就是N/2次。
而我们在描述算法的复杂度给出的是最坏情况，因为这已经是最坏的了，那么剩余的情况肯定就这个好

（4）例子

实例一：

// 计算Func2的时间复杂度？
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{++count;
}
int M = 10;
while (M--)
{++count;
}
printf("%d\n", count);
}

时间复杂度为：O(N)

实例二：

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{++count;
}
for (int k = 0; k < N ; ++ k)
{++count;
}
printf("%d\n", count);
}

若M远大于N则为：O(N)

实例三：

// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{++count;
}
printf("%d\n", count);
}

注意忽略常数项：O(1)

实例四：

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{assert(a);
for (size_t end = n; end > 0; --end)
{int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)break;
}
}

上述是冒泡排序的代码，这里要纠正一点，不要在认为嵌套循环复杂度就是每次循环的次数之积。对于冒泡排序而言，每次排序，都把一个大数排到了最后，所以没趟排序结束之后，下次比较次数就减少一次，也就是1+2+3+4+5+6+·····+N-1,这是一个等差数列，计算其前N项和，得最坏情况的复杂度为O(N²) ，相应的最好情况就是O（N）

实例五：

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n-1;while(begin<end){int mid=begin+((end-begin)>>1);if(a[mid]<x)begin=mid+1;else if(a[mid<x])end=mid;elsereturn mid;}return -1;
}

这是二分查找算法，计算复杂度时不要被循环给误导了，计算时要领会算法的思想。二分查找在查找顺序表时，每次舍弃一半元素，查找一个元素就不断除以2，不断除以2，这样反向过来计算，想要查找到一个长度为N的顺序表中的某个元素时次数就是log₂N，那么复杂度就O(log₂N)

实例六

// 计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t N)
{return N < 2 ? N : Factorial(N-1)*N;
}

这是使用递归计算N的阶乘
对于递归算法，其时间复杂度为：递归次数*每次递归的次数。
故改算法的时间复杂度为O(N)。

实例七

// 计算斐波那契递归Fibonacci的时间复杂度？
long long Fibonacci(size_t N)
{return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

这是斐波那契数列的递归算法
计算Fib(N)，就要计算Fib(N-1)+Fib(N-2)，同理要计算Fib(N-1)就要计算Fib(N-2)+Fib(N-3)，计算Fib(N-2)就要计算Fib(N-3)+Fib(N-4)·······
比如N=5时，可以画出这样形象的图

学完二叉树后，就可以知道这是一颗满二叉树，对于一颗满二叉树每层高度上的结点数(这里结点数就代表斐波那契递归算法递归一次)为2^k-1(这里的k指的是高度)，每层结点数加起来结果就是2ⁿ-1（这里n指的是结点总数），于是斐波那契递归算法的时间复杂度为O(2^N)
这里要注意一下，斐波那契算法生成的满二叉树并不是真正的二叉树，上图中得到很明显的展示，右上角一定会要比左下角的先到1，但是对整体的时间复杂度并没有太大影响。
可以发现计算斐波那契如果使用递归的算法，那么当N比较大时，时间复杂度将会指数级的增长，而且菲薄采用这种算法在计算时其实有一部分计算时完完全全重复了，完全就是在做无用功。所以我们可以采用迭代的方式实现

#include <stdio.h>
#include <stdio.h>
#include <stddef.h>long long* Fibonacci(size_t N)
{long long* fibArray = (long long*)malloc(sizeof(long long)*(N + 1));if (fibArray==NULL){return -1;}fibArray[0] = 0;if (N == 0)return fibArray;fibArray[1] = 1;for (int i = 2; i <= N; i++){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray[N];}int main()
{printf("%d\n", Fibonacci(50));
}

三：空间复杂度

时间复杂度不计算具体的时间，只算大概执行了多少次
空间复杂度不计算具体占用的空间，只计算大概定义的变量个数
实例一

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){ int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)	 break;}
}

共定义了5个变量，故空间复杂度为O(1).
实例二

long long* Fibonacci(size_t n)
{if (n == 0)return NULL;long long * fibArray =(long long *)malloc((n + 1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1; for (int i = 2; i <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;
}

斐波那契数列开辟了N+1个空间，故空间复杂度为O(N)
实例三

// 计算阶乘递归Factorial的空间复杂度？
long long Factorial(size_t N)
{return N < 2 ? N : Factorial(N - 1)*N;
}

阶乘的递归算法递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)