时间与空间复杂度相互影响
服务器君一共花费了403.396 ms进行了6次数据库查询，努力地为您提供了这个页面。
试试阅读模式？希望听取您的建议
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。
我们在写代码时，完全可以用空间来换取时间，比如说，要判断某某年是不是闰年，你可能会花一点心思写了一个算法，而且由于是一个算法，也就意味着，每次给一个年份，都是要通过计算得到是否是闰年的结果。还有另一个办法就是，事先建立一个有2 050个元素的数组（年数略比现实多一点），然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是1，如果不是值为0。这样，所谓的判断某一年是否是闰年，就变成了查找这个数组的某一项的值是多少的问题。此时，我们的运算是最小化了，但是硬盘上或者内存中需要存储这。
算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将快速排序和归并排序算法就属于这种情况。
通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好，其实要看你用在什么地方。
算法的通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)= O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。
当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
对于一个，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。
延伸阅读此文章所在专题列表如下：
本文地址：，欢迎访问原出处。
不打个分吗？
转载随意，但请带上本文地址：
如果你认为这篇文章值得更多人阅读，欢迎使用下面的分享功能。
小提示：您可以按快捷键 Ctrl + D，或点此 。
大家都在看
阅读一百本计算机著作吧，少年
基思(Jeremy Keith) (作者), 桑布尔斯(Jeffrey Sambells) (作者), 魏忠 (合著者), 杨涛 (译者), 王建桥 (译者), 杨晓云 (译者), 等 (译者)
《JavaScript DOM编程艺术(第2版)》内容简介：JavaScript是Web开发中最重要的一门语言，它强大而优美。无论是桌面开发，还是移动应用。JavaScript都是必须掌握的技术。W3C的DOM标准是开发Web应用的基石。已经得到所有现代浏览器的支持，这使得跨平台Web开发成了一件轻松惬意的事。《JavaScript DOM编程艺术(第2版)》是超级畅销书的升级版，由倡导Web标准的领军人物执笔，揭示了前端开发的真谛，是学习JavaScript和DOM开发的必读之作。
扫一扫，在手机上阅读
栏目最新博文
12,249 views
14,603 views
7,239 views
6,968 views
13,083 views
16,267 views
10,705 views
8,942 views
8,278 views
20,258 views
栏目博文推荐
10,205 views
14,603 views
9,676 views
99,688 views
8,425 views
12,154 views
10,524 views
24,159 views
12,067 views
7,932 views
脚步无法到达的地方，目光可以到达；目光无法到达的地方，梦想可以到达。
关于网站与作者
互联网信息太多太杂，各互联网公司不断推送娱乐花边新闻，SNS，微博不断转移我们的注意力。但是，我们的时间和精力却是有限的。这里是互联网浩瀚的海洋中的一座宁静与美丽的小岛，供开发者歇息与静心潜心修炼（愿景）。
“Veda”的本义是知识、启示，希望这里能为开发者提供充足的技术资料。
我的电子邮件gonnsai(，腾讯微博：，欢迎与我联系。posts - 1,&
comments - 0,&
trackbacks - 0
前一段去面试，被问到了时间复杂度和空间复杂度，其实这是两个并不复杂的概念，但是从大学开始就没弄明白，就一直搁浅。。。面试过后大受刺激，决定弥补自己的这段漏洞。
先来说说它们是用来干什么的，举个简单的例子，比如让你计算1+2+3+&&..100，一个简单的程序，相信大部分人抬手就写出了如下代码。
A:& For(i=1;i&101;i++)
&& sum=sum+i;
这段很简单没什么问题，但是计算这个问题还有另一种算法，相信大家还记得数列的求和公式（数学家高斯计算的时候就用的是这个方法），（1+n）n/2，相信大家还记得，首项加末项乘以项数除以2（这句好像有点多余。），如果使用了这个公式的话，算法就变成了。
&&&&&&&&&& B: Sum=(1+100)*100/2
相信大家已经发现了区别，上面的代码运行了100次（也就是N次），下面的代码无论n为几，都只运行了一次，那么这种区别如何描述呢，就引入了时间复杂度这个词。
代表什么意思
时间复杂度可以理解为计算机处理这段代码所需的时间（当然你要抛开硬件问题，不能用286和现在的电脑比运行时间。。），那如何来表示呢。A段代码我们要处理n个数，要运行n次，那么我们用一个函数f(n)来表示代码运行的次数，括号里面的n代表你要处理的数，A段代码中要运行n次，那么对于A来说f(n)=n，同样B段代码，只运行了一行代码，所以f(n)=1，所以我们用f(n)来表示代码运行的次数。
时间复杂度的表达式是 T(n)=O(f(n))，f(n)之前已经解释过了，那么O(f(n))就代表运行f(n)所需要的时间，那么对于A段代码的时间复杂度就表示为O(n)，B段代码为O(1),那么比较A和B，随着n的增大，O(n)明显远大于O(1)。
空间复杂度
这个其实和时间复杂度差不多，空间复杂度的主要作用是用来空间来赢得时间，比如之前从1加到100，如果事先建好了一个数组，里面记录了1到100的值，比如sum[1]=1,sum[2]=3&&&&.sum[100]=5050，那么这样再计算代码A的时候只需要一句代码去数组里面查找key对应的value就可以了，只需要一次查找所以时间复杂度是0(1)，虽然赢得了时间，但是浪费了内存空间，所以空间复杂度为O(n)，到底什么时候需要利用空间换取时间都要根据具体的情况来定。
有不对的地方还希望大家批评指正，互相交流学习。
阅读(...) 评论()中有空间复杂度，它到底与哪些因素有关呀，比如说编译器，数据空间，环境站等等请具体解释一下
全部答案（共3个回答）
中的空间复杂度是对算法所占存储空间的衡量标准，一般只考虑算法所需的额外开销的多少（具体来说就是为完成算法功能需要定义的中间变量、数组等所占存储单元的多少,当然没必要求出具体值，只要给出数量级就可以了），与问题的规模、编译器等无关。
这个题不难
给你一个相似的例子，你照着来吧
一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假...
时间复杂度表面的意思就是代码花费的时间，但是一般使用这个概念的时候，更注重的是随着数据量增长，代码执行时间的增长情况。一般认为一个基本的运算为一次运行算，例如加...
所谓渐进（应该是渐近吧）函数就是y=f（x）中，x无限增大时，y的值无限趋近于某个数，但是始终不会相等。
维斯岛Studio Milna 8490a怎么样？有人住过吗？
答: 如果你理解能力强考数据库，其中比如关系数据库之类的需要去领悟
如果你记忆能力强考网络，各种各样的名词，背下来就得分。
还有官方指定的教材要有，上机最好做一做...
答: 新年好！首先，你必须了解计算机的组成和结构以及操作系统的运作原理，这是基础
如果你想学习开发多线程、WINDOWS应用、动态链接库、WINDOWS组件的话，建...
大家还关注
确定举报此问题
举报原因(必选)：
广告或垃圾信息
激进时政或意识形态话题
不雅词句或人身攻击
侵犯他人隐私
其它违法和不良信息
报告，这不是个问题
报告原因(必选)：
这不是个问题
这个问题分类似乎错了
这个不是我熟悉的地区推荐这篇日记的豆列
&&&&&&&&&&&&欢迎加入我们，一同切磋技术。 &
用户名： &&&
密　码： &
共有 3745 人关注过本帖
标题：算法时间复杂度分析，求上界下界
等　级：论坛游民
帖　子：49
专家分：41
结帖率：50%
&&问题点数：0&&回复次数：1&&&
算法时间复杂度分析，求上界下界
这是书上的一道题：下面的算法段用于确定n的初始值。试分析该算法段所需计算时间的上界和下界。
While(n&1)&&&&&&&&&&&&&&& //&&----- 1
&&& If (odd(n))&&&&&& //&&----- 2
&&&&&& n=3*n+1&&&&&&&&//&&----- 3
&&& else&&&&&&&&&&&&&&//&&----- 4
&&&&&&n=n/2;&&&&&&&&& //&&----- 5
最小复杂度：logN,当N=2^m时，只执行第5行代码，
最大复杂度：klog(3N);N约等于[log(N*3^k)]。
上面是找到的答案，最小复杂度可以理解，请问最大复杂度是怎么计算的？
等　级：论坛游民
帖　子：49
专家分：41
找到答案了，这是3n+1问题，时间复杂度下界是lbN，上界未知，现在还没有答案，所以我找到的那个最大复杂度并不一定正确。
得不到的永远在骚动，被偏爱都有恃无恐
版权所有，并保留所有权利。
Powered by , Processed in 0.103762 second(s), 8 queries.
Copyright&, BCCN.NET, All Rights Reserved