【初阶数据结构与算法】——空间复杂度详解及复杂度OJ练习
3. 空间复杂度
3.1 空间复杂度的概念
空间复杂度又是什么呢？
空间复杂度也是一个问题规模n的函数，是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是计算程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
3.2 常见空间复杂度计算举例
例1.常数次循环
先来看一个简单的：
void Func4(int N) {
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
它的空间复杂度是多少呢？
O(1)
它里面是不是就创建了两个变量啊，count 和k ，那我们说了空间复杂度也使用大O的渐进表示法计算，申请两个变量的空间，常数个，那就是O(1)了。
注意：虽然循环中int k每次循环都创建，但它还是算一个。
例2.冒泡排序
第二个，冒泡排序的空间复杂度：
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)。
我们分析一下，它里面是不是就新定义了3个变量，额外申请了3个变量的空间啊。
那函数参数不算吗？
概念中已经提到了，数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
那3个变量，还是O(1)。
例3.返回斐波那契数列的前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;
}
答案是O(N)
我们它里面动态申请了一个数组，n + 1个元素，另外还有几个变量，像指针变量long long* fibArray，for循环中还有个int i = 2，但还是常数个N+几，我们可以不用管，所以就是O(N)。
例4.递归求阶乘
再看一个：
long long Fac(size_t N) {
if (N == 1)
return 1;
return Fac(N - 1) * N;
}
这个是多少？
O(N)
递归调用了N次，开辟了N个函数栈帧（最后返回时才会逐一销毁），每个栈帧使用了常数个空间。空间复杂度为O(N)
例5. 递归求斐波那契第N项
long long Fib(size_t N) {
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
该算法的时间复杂度我们求过了是O(2^N)，那空间复杂度呢？
是
O(2^N)吗，不是的，它的空间复杂度是O(N)。为什么呢？
时间是一去不复返的，是累加的，但是空间是可以重复利用的。
什么意思呢？
这是我们计算时间复杂度是分析的图，它递归调用了这么多次，但是，这么多分支，它们进行递归，开辟函数栈帧，是同时进行吗？
不是的。
它们是一个分支，一个分支按照先后顺序进行的。
Fib(N )=Fib(N - 1) + Fib(N - 2)
Fib(N - 1)递归调用完，才会开始Fib(N - 2)，它们会重复利用同一块空间。
最长的那个分支同时建立N个函数栈帧，所以空间复杂度为O(N)
4. 常见复杂度对比
5. 复杂度的oj练习
5.1 消失的数字
链接: link
链接放这里，大家可以自己做一下。
这里给两种解法：
1. 0到n求和减去数组元素之和
2. 让0和0到n异或，异或的结果和数组元素异或，最终得到的结果就是缺失的那个数字。
原理：0和任何数异或结果还是这个数，两个相同的数字异或结果为0。
上代码：
int missingNumber(int* nums, int numsSize){
//思路一：0到n求和减去数组元素和
// int i=0;
// int sum=0;
// for(i=1;i<=numsSize;i++)
// {
// sum+=i;
// }
// int j=0;
// for(j=0;j<numsSize;j++)
// {
// sum-=nums[j];
// }
// return sum;
//思路二：单身狗问题
int i=0;
int x=0;
//x=0和0到n异或
for(i=1;i<=numsSize;i++)
{
x^=i;
}
//x和数组元素异或
int j=0;
for(j=0;j<numsSize;j++)
{
x^=nums[j];
}
return x;
}
5.2 轮转数组
链接: link
还是给两种解法：
1. 再创建一个同样大小的数组，把需要轮转的元素放在数组前面，然后把剩余元素放到数组后面，再拷贝到原数组中。
另外需要注意，如果N个元素的数组，你轮转N次是不是就还和原来的一样，而且K如果太大，大于 题中的numSize，下标为负，还会越界访问，所以加上一句k%=numsSize;
void rotate(int* nums, int numsSize, int k)
{
k%=numsSize;
int arr[numsSize];
int i=0;
int j=0;
//需要轮转的元素放在数组前面
for(i=numsSize-k;i<numsSize;i++)
{
arr[j]=nums[i];
j++;
}
//剩余元素放到数组后面
for(i=0;i<numsSize-k;i++)
{
arr[j]=nums[i];
j++;
}
//拷贝到原数组中
j=0;
for(i=0;i<numsSize;i++)
{
nums[j]=arr[i];
j++;
}
}
先将前n-k个元素进行逆序，然后将剩余元素进行逆序，最后再逆序整个数组。
void reverse(int* start, int* end)
{
while (start < end)
{
int tmp = *start;
*start = *end;
*end = tmp;
start++;
end--;
}
}
void rotate(int* nums, int numsSize, int k)
{
//向右轮转numsSize次相当于没轮转
k %= numsSize;
reverse(nums, nums + numsSize - 1 - k);
reverse(nums + numsSize - k, nums + numsSize - 1);
reverse(nums, nums + numsSize - 1);
}
好了，以上就是这篇文章的全部内容，欢迎大家指正！！！
- 点赞
- 收藏
- 关注作者
评论（0）