算法 空间复杂度
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了算法 空间复杂度,现在分享给大家,供学习和参考。文章包含550字,纯文字阅读大概需要2分钟。
教程信息
1、算法的渐进空间复杂度
类似于时间复杂度的讨论,一个算法的空间复杂度是该算法所耗费的存储空间,随输入规模增长而增长的趋势。
一个算法在计算机存储器上所占用的存储空间,包括
存储算法本身所占用的存储空间,
算法的输入输出数据所占用的存储空间
算法在运行过程中临时占用的存储空间
这三个方面。
(1)算法的输入输出数据的存储空间
由要解决的问题决定的,不随本算法的不同而改变。
(2)存储算法本身的存储空间
与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法
(3)算法在运行过程中临时占用的存储空间
随算法的不同而异,也就是需要讨论的空间复杂度
一般来说,
空间复杂度 O(1)指没有用到数组,
空间复杂度 O(n)指用到一维数组,
空间复杂度 O(n2)指用到二维数组。
一般的递归算法因为要使用递归栈,有O(n)的空间复杂度。
2、原地算法
如果一个算法在运行过程中临时占用的存储空间是小的
、且不随着问题规模影响
的,我们可以称作“就地算法/原地算法
”。不是原地算法有时候称为非原地算法
。
3、与时间复杂度的区别
空间复杂度并不总是决定算法好坏的关键因素。有些情况下,空间复杂度高但时间复杂度低的算法可能更优秀,因为它可以在较短的时间内完成任务,
而在现代计算机的存储容量越来越大的情况下,空间的成本相对时间成本越来越低。
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供算法 空间复杂度的全部内容,希望教程文章能够帮你了解学习算法 空间复杂度,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaozhongji-256.html