数据结构-算法的空间复杂度(1.2)
目录
1.1 例子
1.2 空间的特殊性质
写在最后:
1.空间复杂度
空间复杂度也是一个数学表达式,
是对一个算法在运行过程中临时占用存储空间大小的量度。
他也是用大O渐进表示法。
1.1 例子
例1:
冒泡排序:
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)。
例2:
斐波那契数列:
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;
}
这里用malloc开辟了n个以上的空间,
所以它的空间复杂度是O(N)。
例3:
阶乘递归:
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}
这段代码,
因为函数递归,建立函数栈帧,
而函数栈帧里有常数个(空间)变量开辟,
而这段代码,建立了N+1个函数栈帧,
所以它的空间复杂度是O(N)。
1.2 空间的特殊性质
例4:
long long Fib(int N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
这段代码的时间复杂度是O(2的N次方)。
但是,它的空间复杂度呢?
实际上,他的空间复杂度是O(N),而不是O(2的N次方)。
为什么呢?
因为函数递归的过程中会建立栈帧,而这段代码在进行递归的时候,
并不会一直递归到最后才返回,
当它递归到一定程度是,会有函数提前返回,
导致栈帧销毁,当新的栈帧建立的时候,
空间就会被重复使用,
例:
#include <stdio.h>void f1()
{int b = 0;printf("%p\\n", &b);
}void f2()
{int a = 0;printf("%p\\n", &a);
}int main()
{f1();f2();return 0;
}
输出:
我们发现,当f1函数的栈帧销毁后,
f2函数栈帧建立,创建的变量地址与f1中创建的变量地址相同,
这就是空间重复利用的特性。
例:
#include <stdio.h>void f1()
{int b = 0;printf("%p\\n", &b);
}void f2()
{int a = 0;printf("%p\\n", &a);f1();
}int main()
{f2();return 0;
}
输出:
当f1函数的栈帧没有销毁,
f2函数的变量自然用不了f1函数的空间,
所以他们的地址当然不同了。
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。
之后我还会输出更多高质量内容,欢迎收看。