【数据结构和算法初阶(C语言)】空间复杂度(例题剖析一起探究空间如何评价算法）

03-07 1476阅读

1.衔接前言-时间复杂度的回顾

2.关于算法复杂度

3.本文主角-空间复杂度

3.1大O的渐进表示方法

4.空间复杂度例题----实际感受空间复杂度

4.1冒泡排序的空间复杂度

4.2计算递归函数的空间复杂度

4.3动态开辟内存版本求斐波那契数列的空间复杂度

4.4（重要难点理解）求斐波那契数列递归算法的时间复杂度（注意空间复用）

5.常见复杂度对比

6.关于空间复杂度的oj题目练习-旋转数组

6.1思路1

6.2思路2

6.2.1k%n的重要性-----oj题目中的越界错误

6.3思路3-----旋转旋转再旋转

7.结语

1.衔接前言-时间复杂度的回顾

时间复杂度复习跳转

2.关于算法复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，
而空间复杂度主要衡量一个算法运行所需要的额外空间。
在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
3.本文主角-空间复杂度
- 空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度
- 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。形式参数不算。
- 空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
- 注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。但是如果在运行期间额外调用堆栈要算
  3.1大O的渐进表示方法
  - 这个表示方法在时间复杂度讲过大家也可以先看完时间复杂度在过来。
  - 1、用常数1取代运行时间中的所有加法常数。
  - 2、在修改后的运行次数函数中，只保留最高阶项。
  - 3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
    我们直接上代码来带入理解时间复杂度的计算方法：
    
    4.空间复杂度例题----实际感受空间复杂度
    
    重点：
    
    运行过程中临时占用存储空间大小的量度
    
    ①空间复杂度算的运行过程中开辟的变量的个数。开辟的变量要满足要求就是为了实现这个算法，形式参数不算。
    
    ②运行期间额外调用堆栈要算
    
    4.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  a[i])
 {
 Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;
 }
}
```
    那我们首先看一下我们调用这个算法，会创建那几个变量：
    
    如
    - ①所示：end、exchange、i这三个变量就是我们的为了实现算法而创建的变量，分别为了实现我们算法中的循环、迭代等功能。所以按照大O的渐进表示法，这个算法的空间复杂度就是O(3),但是，根据第一条：用常数1取代运行时间中的所有加法常数。所以这个冒泡排序算法的空间复杂度表示为O(1).
    - ②这是一个形式参数，不算做空间复杂度的计算对象
    - ③这是一个指针参数，指向一个数组，很多伙伴会想这个数组的空间要不要算作空间复杂度的计算之中，实际上是不必要的，我们要牢牢扣住空间复杂度的定义，为了实现算法而额外开辟的空间才纳入计算，那么如果我们不是为了实现这算法而是要调用其他算法，那么这个数组的空间照样要上传到其他算法1，所以这个数组的空间就不算做时间复杂度的值内。
      4.2计算递归函数的空间复杂度
```
long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}
```
      4.3动态开辟内存版本求斐波那契数列的空间复杂度
```
// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
 if(n==0)
 return NULL;
 
 long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i 
```