一、
-
什么是数据结构：
在内存当中管理数据。
-
算法复杂度：时间和空间
时间复杂度 主 要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间 。
时间复杂度：一个算法运行之中的次数（函数调用、循环），类似于数学中的函数式。
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要 大概执行次数，那么这里我们使用 大 O 的渐进表示法。O（）
法则：
1.保留最高阶项，将小一个量级的全舍弃（比如N*logN+N要舍弃N，变成N*logN）
2.同阶全保留
3.O（1）表示常数次，而不是1次
4.同阶系数忽略掉，2*N 变成O（N）（当一次程序需要两个N才能执行完时，时间复杂时O（N），不是2*N）
5.不确定次数的算法，按最坏情况O（N）确定算法复杂度 了 （ M+N次，有两个未知数M和N，时间复杂度为 O(N+M) ）
6.计算循环（循环几次）和递归（调用几次）次数，不考虑其他
常见阶数：
常数、线性、平方、立方、次方、对数、N*logN、指数函数阶
//暴力查找O（N） ；冒泡排序 O(N*N)； qsort O(N*log2N) ; 二分查找 O(Log2N)
空间复杂度：
也是一个数学表达式，也用 ！!O渐进表示法! !。
计算量：
1.额外开辟的数组、变量、动态内存、函数等空间
2.形参不算
3.函数运行时所需要的栈空间 ( 存储参数、局部变量、一些寄存器信息等 ) 在编译期间已经确定好了，因
此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定
4.栈帧的计算
long long Fac ( size_t N )
{
if ( N == 0 )
return 1 ;
return Fac ( N - 1 ) * N ;
}
递归调用了 N 次，开辟了 N 个栈帧，每个栈帧使用了常数个空间（如：寄存器等....（但是由于是常数个·都可以不算进去））。空间复杂度为 O(N)
斐波那契数列的空间复杂度： 空间O（N）
原因：
Fib(n - 1)调用时，会持续调用栈帧，只调用一条支路，最多N个，调用完之后，销毁之后，Fib（n -2）会重复使用第一次调用出来的N个栈帧的空间（会复用栈帧空间）！
理解：空间的销毁是归还使用权，不是彻底摧毁空间！
总结：
时间一去不复返（累计计算）、空间可以重利用（不累积计算）！
