【数据结构】详解空间复杂度

                                

Yan英杰的博客

                                                        悟已往之不谏 知来者之可追

---

目录

空间复杂度

​案例1:计算BubbleSort的空间复杂度？       

案例2:计算斐波那契额数列的前N项的空间复杂度

案例3:计算阶乘递归Fac的空间复杂度？

案例4:F1和F2两函数是否使用的同一块空间

案例5:计算该程序的空间复杂度

案例6:经典OJ(难度中等)

---

空间复杂度

        

        空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。

        空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

        

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

案例1:计算BubbleSort的空间复杂度？       

        

// 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;}
}

分析:

                        注：空间复杂度本质是:计算因为程序导致额外开辟的空间个数

                        

                        此时，该程序额外开辟了，三个变量，end exchange i，又因为空间复杂度同样使用的是大O表达式，所以我们由此得出，空间复杂度为O(N)

提问:

                        当时我在计算该程序的空间复杂度，有个疑问，为什么不把数组算进去

                        这是因为，我们在计算之前，就已经开辟了数组的栈帧空间，开始前就给出了，所以不用在空间复杂度内加上数组的大小

案例2:计算斐波那契额数列的前N项的空间复杂度

//计算斐波那契额数列的前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 <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;
}

        分析:

                我们当前的变量为0，但是我们要求第N项的空间复杂度，所以我们开辟了n+1块空间，用来计算前N项和的空间复杂度，O(N+1)为其空间复杂度，但是大O的渐进表示法，我们计算出斐波那契额数列前N项和的空间复杂度为O(N)

 案例3:计算阶乘递归Fac的空间复杂度？

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

分析：

由于该程序为递归，导致因为程序我们需要不断的开辟新的栈帧空间(每次传参均需要开辟一块新的空间)维护，所以此程序的空间复杂度为O(N)

提问:

为什么开辟栈帧空间后需要额外再开辟新的栈帧空间？

主要是因为，栈帧空间只有在函数结束后,才会销毁，而递归时，函数其实并未销毁，这也导致了其不断开辟新的栈帧空间，也因为该程序的空间复杂度为O(N)       

图解:

案例4:F1和F2两函数是否使用的同一块空间

//F1和F2两函数是否使用的同一块空间
void F2()
{int b = 0;printf("%p\n",&b);
}
void F1()
{int a = 0;printf("%p\n",&a);
}int main()
{F1();F2();return 0;
}

解析: 

        当调用F1函数时在Main函数低地址处进行压栈，当出了F1函数，函数销毁，同时它用过的栈帧空间返回到内存中，当我们再调用F2时，F2继续在Main函数低地址处压栈，所以他俩所维护的栈帧空间其实是同一块

图解:

 提问:

        那如何修改，才能使两个函数指向不同栈帧空间？

分析:

       当我们在F1中调用F2时，使得F1函数无法释放栈帧空间，F2就必须在F1低地址处压栈，此时他们两个维护的栈帧空间则不相同

图解：

案例5:计算该程序的空间复杂度

//计算该程序的空间复杂度
long long Fib(size_t N)
{if (N<3){return 1;}return Fib(N-1) - Fib(N-2);
}

  解析：

为了详解这道题，我们要先清楚其时间复杂度如何计算

由此看出其时间复杂度为O(2^N)

         

当我们弄懂其时间复杂度后，以该时间复杂度为原型，上面为什么要弄懂，函数维护的空间其实也是有原因的，当Fib(2)销毁后，调用Fib(1)，我们可以由此看出，其实Fib(2)和Fib(1)维护的是同一块栈帧空间,销毁后再返回到上一次，再销毁，再调用其他函数，其实总共维护的栈帧空间为N块

图解:

                

                注:时间一去不复返无法重复利用，但是空间用了之后归还，可以重复利用

案例6:经典OJ(难度中等)

          示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

        示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

解析:

我们可以对其进行翻转，前k项进行翻转，后N-k进行翻转，最后进行整体翻转

        图解：

        

            错误示范:

                        

void reverse(int* nums,int begin ,int end)
{while (begin < end){int tmp = nums[begin];nums[begin] = nums[end];nums[end] = tmp;begin++;end--;}}
void rotate(int* nums, int numsSize, int k)
{reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums, 0, numsSize - 1);
}

  错误原因:

当数组的输入的个数，小于输入的数组大小，就会出现数组越界访问的问题，所以导致了报错

解决办法：

void reverse(int* nums,int begin ,int end)
{while (begin < end){int tmp = nums[begin];nums[begin] = nums[end];nums[end] = tmp;begin++;end--;}}
void rotate(int* nums, int numsSize, int k)
{if (k > numsSize){k %= numsSize;}reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums, 0, numsSize - 1);
}