承接上文，《数据结构》时间复杂度

空间复杂度相对于比较时间复杂度就变得非常简单了

相比而言现在算法不那么关注空间复杂度，因为现在的设备的存储空间都比较大。

一、大O渐进表示法

 我们重新来回忆一下大O渐进法

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

二、空间复杂度计算方法

        空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

        函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

三、空间复杂度练习

void bubbleSort(int[] array) {
    for (int end = array.length; end > 0; end--) {
        boolean sorted = true;
    for (int i = 1; i < end; i++) {
        if (array[i - 1] > array[i]) {
            Swap(array, i - 1, i);
                sorted = false;
        }
    }
        if (sorted == true) {
                break;
        }
    }
}

我们已经知道，空间复杂度是计算运行过程中开辟的临时空间

代码在运行中开辟了常数个额外空间，所以空间复杂度为 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;
    }
}

 冒泡排序的空间复杂度为：O(1)

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}

  阶乘递归的时间复杂度：O(N).

 我们总结了如下的算法时间空间复杂度

我们可以看到对排序法的颜色有区别 在紫色标注的为简单排序，其余的为高级排序 

希望能对大家有帮助