算法时间空间复杂度计算—空间复杂度

空间复杂度定义

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
一个算法在计算机存储器上所占用的存储空间，包括程序代码所占用的空间，输入数据所占用的空间和辅助变量所占用的空间这三个方面。

影响空间复杂度的因素

注意：
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变 量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小。它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)
递归的空间复杂度： 每次递归所开空间*深度。

算法在运行过程中临时占用的存储空间讲解

1、有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地”进行的，是节省存储的算法，下面会介绍。

2、有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。

计算方法

①忽略常数，用O(1)表示
②递归算法的空间复杂度=递归深度n*每次递归所要的辅助空间
③对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。

例子

1、空间算法的常数阶

如上图，这里有三个局部变量分配了存储空间，所以f(n) = 1 + 1 + 1 = 3，根据上面的法则该函数不受n的影响且为常数项，所以空间复杂度记作O(1)。这种与问题的大小无关（n的多少），执行时间恒定的算法，我们称之为具有O(1)的空间复杂度，又叫常数阶。

2、空间算法的线性阶（递归算法）

如上图，这是一个递归算法（计算从n + (n-1) + (n-2) + … + 2 + 1的和）
每当执行一次该函数就会为tmp分配一个临时存储空间，所以f(n) = 1*(n-1+1) = n，函数是受n影响的所以空间复杂度记为O(n)。

3、二分查找分析

方法一（迭代法）

	/// <summary>
    /// 二分查找
    /// </summary>
    /// <param name="arr">查找数组</param>
    /// <param name="len">数组长度</param>
    /// <param name="num">查找项</param>
    /// <returns></returns>
    int BinarySearch(int[] arr,int len,int num)
    {
        int left = 0;
        int right = len - 1;
        int mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (arr[mid] > num)
                right = mid - 1;
            else if (arr[mid] < num)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }

时间复杂度：
left、right、mid运算次数
f(n1) = 1 + 1 + 1 = 3
我们将While循环中的运算作为一个整体看待，每次都是折半运算次数
f(n2) = log2^n
总运行次数
f(all) = f(n1)+f(n2) = 3 + log2 ^ n
时间复杂度记为:O(log2^n)

---

空间复杂度：
算法中left、right、mid只创建的次数
s(n) = 1 + 1 + 1 = 3
空间复杂度记为:O(1)

方法二（递归法）

 /// <summary>
    /// 二分查找(递归法)
    /// </summary>
    /// <param name="arr"></param>
    /// <param name="left"></param>
    /// <param name="right"></param>
    /// <param name="num"></param>
    /// <returns></returns>
    int BinarySearchRecursion(int[] arr,int left,int right,int num)
    {
        int mid = (left + right) / 2;
        if (left <= right)
        {
            if (arr[mid] > num) {
                right = mid - 1;
                return BinarySearchRecursion(arr,left,right,num);
            }
            else if (arr[mid] < num)
            {
                left = mid + 1;
                return BinarySearchRecursion(arr,left,right,num);
            }
            else
                return mid;
        }
        else
        {
            return -1;
        }
    }

时间复杂度：
运行次数 f(n) = log2 ^ n
时间复杂度记为:O(log2^n)

---

空间复杂度：
因为整个算法中mid只创建的次数
s(n) = log2 ^ n
空间复杂度记为:O(log2 ^ n)

---

4、斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
这个数列从第3项开始，每一项都等于前两项之和。

如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：:F(n)=F(n-1)+F(n-2)

显然这是一个线性的递推数列。
通项公式 ：

上面就是斐波那契数列的递推公式，这样一个完全是自然数的数列，通项公式却是用无理数来表达的。而且当n趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割0.618

递推是公式是求解斐波那契数列的一个方法，我们当然也可以用计算机编写程序来求解。

方法一（迭代法）

  /// <summary>
    /// 斐波那契（迭代法）
    /// </summary>
    /// <param name="n"></param>
    /// <returns></returns>
    int Fibonacci(int n)
    {
        if (n <= 0)
            return -1;
        if (n == 1 || n == 2)
            return 1;
        else
        {
            int num = 0;
            int a = 1;
            int b = 1;
            while (n - 2 > 0)
            {
                num = a + b;
                a = b;
                b = num;
                n--;
            }
            return num;
        }

    }

时间复杂度：
while以外的算法语句都忽略不计(不随n的变化而变化)
while算法语句所有语句
f(n) = 4 *（n - 2） = 4n - 8
时间复杂度记为:O(n)

---

空间复杂度：
算法中num、a、b只创建1次
s(n) = 1 + 1 + 1 = 3
空间复杂度记为:O(1)

---

方法二（递归法）

/// <summary>
    /// 斐波那契（递归法）
    /// </summary>
    /// <param name="n"></param>
    /// <returns></returns>
    int FibonacciRecursion(int n)
    {
        if (n <= 0)
            return -1;
        if (n == 1 || n == 2)
            return 1;
        return FibonacciRecursion(n - 1) + FibonacciRecursion(n - 2);
    }

时间复杂度：
递归调用的形参有两个n - 1 和 n - 2
时间复杂度记为:O(2^n)

---

空间复杂度：
递归的空间复杂度 =（n + 1）* 调用的深度
空间复杂度记为:O(n)（这里可以简单的根据二叉树的层来进行计算）

---