为了账号安全,请及时绑定邮箱和手机立即绑定
慕课专栏

目录

索引目录

Python 算法科普指南

原价 ¥ 48.00

立即订阅
03 这个算法为啥占了这么大空间?
更新时间:2019-12-09 19:06:25
从不浪费时间的人,没有工夫抱怨时间不够。

——杰弗逊

空间复杂度

js123.com_【官方首页】-澳门金沙一个算法在计算机存储器上所占用的存储空间,包括算法本身所占用的存储空间,算法的输入、输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

算法本身所占用的存储空间由算法本身的长度决定。在大多数情况下,算法自身占用的空间对于算法整体的空间复杂度的影响有限。毕竟一个手写的算法的长度是有限的,而代码用字符串的方式存储,不会占用过多空间。

在绝大多数情况下,算法的输入、输出数据所占用的存储空间是由要解决的问题决定的,它不随着算法的不同而改变。js123.com_【官方首页】-澳门金沙算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且这些临时工作单元不随问题规模的大小而改变,有的算法需要占用的临时工作单元数量与解决问题的规模 n 有关,它随着 n 的增大而增大,当 n 较大时,将占用较多的存储单元,例如快速排序和归并排序就属于这种情况。

而空间复杂度就是对一个算法所需存储空间的量度,但其并不考虑算法本身所占用的存储空间。若算法的输入、输出数据所占用的存储空间只取决于问题本身,则也不列入考虑范围中。因为后两个因素并不能精准的体现一个算法的优劣。类似于时间复杂度,空间复杂度也是自变量为输入规模的函数,并考察输入规模趋于无穷时所占用空间的渐近情况,所以空间复杂度也用大 O 符号来表示,记做

S(n)=O(f(n))S(n) = O(f(n))

比如直接插入排序的时间复杂度是O(n2)O(n^2),而空间复杂度是 O(1)O(1),因为插入排序只是在已存储好的数组或列表上进行排序,不需要额外存储临时变量。而一般的递归算法就要有 O(n)O(n) 的空间复杂度了,因为每次递归都要存储返回信息,否则大部分递归运算都在做无用功。

时间复杂度和空间复杂度往往是相互制约,相互影响的。在解决同一个问题的时候,当追求降低时间复杂度时,可能会不可避免地提高空间复杂度,即可能导致占用较多的存储空间;反之,当追求降低空间复杂度时,可能会不可避免地提高时间复杂度,即可能导致占用较长的运行时间。所以在设计一个算法的同时,要综合考虑算法的各项性能,从而更有效地提高效率。

Python算法的优势

js123.com_【官方首页】-澳门金沙目前,Python已经发展成为世界上最受欢迎的编程语言之一,使用非常广泛。js123.com_【官方首页】-澳门金沙由于其语言的简洁性和丰富的第三方库,相比其他编程语言,使用Pyhton编程会更加容易。

Pyhton是一种非常高级的语言,为我们提供了很多高级的数据结构和相关操作,例如列表这一数据结构就比其他语言的类似结构使用起来方便很多。js123.com_【官方首页】-澳门金沙同样,针对不同算法,Python也提供了像集合、字典等非常高效的数据结构,操作非常简单,可以直接使用。这一点,不像其他语言,例如C语言,只提供数组、指针等低级的数据结构,为了实现一些算法,还需要我们自己编写相应的增删改查方法。使用Python语言学习算法,往往起到事半功倍的效果。

使用Python学习算法,最大的优势就是可以看到复杂的算法是怎样一步步地从基本的语言机制实现出来。或者说由于Pyhton语法的简洁,使得编写算法不用拘泥于复杂的语法,而更关注算法的思想本身。而这不就是学习算法的目的吗?

小结

空间复杂度同样是衡量一个算法优劣的标准。对于空间复杂度,因为绝大多数算法需要占用的临时工作单元数量与解决问题的规模也就是输入规模 n 有关,所以输入规模不但影响了算法对于输入数据的存储空间,还影响了算法临时占用的空间。

算法在现实的应用有很多,而有更多的高效算法需被开发。算法在生活中无处不在,意义非凡。下图为常见排序算法的复杂度汇总,如表1-1所示。

表1-1 常见算法总结

排序算法 平均时间复杂度 最优时间复杂度 最差时间复杂度 空间复杂度
选择排序 O(n2)O (n^2) O(n2)O (n^2) O(n2)O (n^2) O(1)O(1)
插入排序 O(n2)O (n^2) O(n)O (n) O(n2)O (n^2) O(1)O(1)
冒泡排序 O(n2)O (n^2) O(n2)O (n^2) O(n2)O (n^2) O(1)O(1)
快速排序 O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(n2)O (n^2) O(nlogn)O(nlogn)
堆排序 O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(1)O(1)
归并排序 O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(nlogn)O(nlogn) O(n)O (n)
}
立即订阅 ¥ 48.00

你正在阅读课程试读内容,订阅后解锁课程全部内容

千学不如一看,千看不如一练

手机
阅读

扫一扫 手机阅读

Python 算法科普指南
立即订阅 ¥ 48.00

举报

0/150
提交
取消

页面底部区域 foot.htm