找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法空间复杂度

admin 2019-6-5 11:23 130人围观 C++相关



复习一下与时间复杂度对应的空间复杂度。

空间复杂度指的就是算法在执行过程中所用的空间大小的量度,一个算法使用主要从算法的执行时间和所需要占用的存储空间两个方面选择使用。

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,看作一个有关n的函数:S(n)=O(f(n)),还是取高阶项。

比如冒泡排序,我们使用一个变量就行了,不会随着n的变化而变化,所以的空间复杂度是O(1)。一个算法不同的人有不同的实现,所以就算是冒牌排序,不同的写法可能复杂度就不通啦。



鱼和熊掌不可兼得,有得必有失。对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差。




----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:南蝶wind,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......