版本记录

版本号	时间
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. 斐波那契数的时间复杂度、空间复杂度详解