版本记录
| 版本号 | 时间 |
|---|---|
| V1.0 | 2018.09.14 |
前言
关于算法学习有很多很基础的概念和理论，我们不需要强行记忆但是一定要理解明白和说的出来，这个专题就是专门进行有关算法基本内容的一些解析。感兴趣的可以看下面几篇。
1. 算法基础（一） —— 时间复杂度研究（一）
空间复杂度
首先我们看一下空间复杂度的概念。
官方解释：空间复杂度
(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1)。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作:S(n)= O(f(n))，其中，n为问题的规模， f(n)为语句关于 n 所占存储空间的函数。
一般情况下， 一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元，若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。
计算方法
- 忽略常数，用
O(1)表示。 - 递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间。
- 对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。
下面看一下各种排序算法的时间复杂度和空间复杂度。
计算示例
下面我们就看一下空间复杂度的计算示例。
1. O（1）
int a;
int b;
printf("%d %d\n",a,b);
这个的空间复杂度就是O（n）= O（1），因为这个空间复杂度的是一个常数。
2. O（n）
int fun(int n)
{
int k = 10;
if(n == k){
return n;
}
else{
return fun(++n);
}
}
递归实现，调用fun函数，每次都创建1个变量k。调用n次，空间复杂度为O（n)。
3. 斐波那契数列
递归
int fib1(int n)
{
while (n < 2)
return n;
while (n >= 2)
return fib1(n - 1) + fib1(n - 2);
}
空间复杂度为O(1)。
要想求解F(n)，必须先计算F(n-1)和F(n-2)，计算F(n-1)和F(n-2)，又必须先计算F(n-3)和F(n-4).....以此类推，直至必须先计算F(1)和F(0)，然后逆推得到F(n-1)和F(n-2)的结果，从而得到F(n)要计算很多重复的值，在时间上造成了很大的浪费，算法的时间复杂度随着N的增大呈现指数增长，时间的复杂度为O(2^n)，即2的n次方。
整个程序执行过程中，最多占用4个函数栈帧空间的大小，设一个函数栈帧空间为C。因此可得知当n=5时，该程序空间复杂度为O(4C)=>O(1)当求第n个斐波那契数时，程序空间复杂度为O(n-1)C (n是常数)=>O(1)。
非递归
long long fib2(int n)
{
int i = 0, f1 = 1, f2 = 1, f3 = 0;
if (n < 2)
return n;
if (n >= 2)
for (long long i = 2; i <= n; i++)
{
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}
空间复杂度为O(n)。
从n(>2)开始计算，用F(n-1)和F(n-2)两个数相加求出结果，这样就避免了大量的重复计算，它的效率比递归算法快得多，算法的时间复杂度与n成正比，即算法的时间复杂度为O(n)。
尾递归的方法，需开辟n-2个空间，空间复杂度为O(n-2)即O(n)。
参考文章
1. 以斐波那契数列为例分析递归算法的时间复杂度和空间复杂度
2. 斐波那契数的时间复杂度、空间复杂度详解
