一个算法的时间复杂度和其空间复杂度有何关系

1. 一个算法的时间复杂度和其空间复杂度有何关系

一个算法的时间复杂度和其空间复杂度的关系可这样理解。
一个算法要做高效率低存储是很困难的，也就是说，算法的时间复杂度小，可能需要较大的空间复杂度。反之亦然。也可以说，通过空间换得时间。
算法的时间复杂度和空间复杂度可以同时很大，也可以同时很小。如T(n)=O(n)且S(n)=O(1)的情况比如一个for(i=0;i<N;i++)，若循环体中为一个与问题规模无关的变量变化，则其S(n)=O(1)，而T(n)=O(n)是随着N的变化而变化的，这时可以说时间复杂度较小而空间复杂度很小。

扩展资料：
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。
参考资料来源：百度百科-空间复杂度

2. 有没有人会分析计算一段算法的时间复杂度跟空间复杂度的？高分跪求！

算法的复杂性 

算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。

计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。 

不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 

简言之，在算法学习过程中，我们必须首先学会对算法的分析，以确定或判断算法的优劣。

1.时间复杂性：
例1：设一程序段如下（为讨论方便，每行前加一行号）
(1) for i:=1 to n do
(2) for j:=1 to n do
(3) x:=x+1
  ......
  试问在程序运行中各步执行的次数各为多少？
  解答：
行号 次数(频度)
(1)   n+1
(2)   n*(n+1)
(3)   n*n
  可见，这段程序总的执行次数是：f(n)=2n2+2n+1。在这里，n可以表示问题的规模，当n趋向无穷大时，如果   f(n)的值很小，则算法优。作为初学者，我们可以用f(n)的数量级O来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。

2.空间复杂性:

例2:将一一维数组的数据(n个)逆序存放到原数组中,下面是实现该问题的两种算法:

算法1:for i:=1 to n do

       b[i]:=a[n-i+1];

     for i:=1 to n do

       a[i]:=b[i];

算法2:for i:=1 to n div 2 do

        begin

       t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t

        end;

算法1的时间复杂度为2n,空间复杂度为2n

算法2的时间复杂度为3*n/2,空间复杂度为n+1

显然算法2比算法1优，这两种算法的空间复杂度可粗略地表示为S(n)=O(n)

信息学比赛中，经常是：只要不超过内存，尽可能用空间换时间。
另外,站长团上有产品团购,便宜有保证

3. 算法的时间复杂度和空间复杂度怎么看

时间复杂度，就是计算程序运行的时间，空间复杂度， 就是所占的内存空间。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

4. 估算算法时间复杂度的方法

就是根据程序运行的最基本的操作的次数，记为T（n）
例：算法： 
 
　　for（i=1;i<=n;++i） 
 
　　{ 
 
　　for(j=1;j<=n;++j) 
 
　　{ 
 
　　c[ i ][ j ]=0; //该步骤属于基本操作 执行次数：n的平方 次 
 
　　for(k=1;k<=n;++k) 
 
　　c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数：n的三次方 次 
 
　　} 
 
　　} 
 
　　则有 T（n）= n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方 为T（n）的同数量级 
 
　　则有f（n）= n的三次方，然后根据T（n）/f（n）求极限可得到常数c 
 
　　则该算法的 时间复杂度：T（n）=O（n^3） 注：n^3即是n的3次方。

5. 时间复杂度的算法复杂度

算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度）。

6. 如何清晰的理解算法中的时间复杂度

求解算法的时间复杂度的具体步骤是：　　⑴找出算法中的基本语句；　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。　　⑵计算基本语句的执行次数的数量级；　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。　　⑶用大Ο记号表示算法的时间性能。　　将基本语句执行次数的数量级放入大Ο记号中。　　如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：　　for(i=1;i<=n;i++)　　x++;　　for(i=1;i<=n;i++)　　for(j=1;j<=n;j++)　　x++;　　第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。　　常见的算法时间复杂度由小到大依次为：　　Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。这只能基本的计算时间复杂度，具体的运行还会与硬件有关。

7. 算法：时间复杂度的计算

2[2T(N/2^2)+cN/2]+cN=4T(N/2^2)+2cN
而T(N/2^2)=2T(N/2^4)+cN/2^2]
代入上式
然后一直迭代下去
就可得到
2^kT(1)+ckN
由N/2^k=1可知，2^k=N。
带入上面式子可得
NT(1)+cNlogN

8. 时间复杂度及其计算

 算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着 用系统的方法描述解决问题的策略机制 。对于同一个问题的解决，可能会存在着不同的算法，为了衡量一个算法的优劣，提出了空间复杂度与时间复杂度这两个概念。
   一个算法是由 控制结构（顺序、分支和循环3种） 和 原操作（指固有数据类型的操作） 构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是：   从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。

   参考文章： 算法的时间复杂度和空间复杂度-总结    时间复杂度，又称时间频度，即 一个算法执行所耗费的时间 。
   一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)
   n称为 问题的规模 ，当n不断变化时，时间频度T(n)也会不断变化。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示， 若有某个辅助函数f(n),使得当n趋近于无穷大时，*T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。
   算法中语句执行次数为一个常数，则时间复杂度为O(1)。常见的时间复杂度有：
常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(n log2n),平方阶O(n2)，立方阶O(n3),...。   Log28：2为底N的对数，即2的几次方等于8，值为3        常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(n log2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)   即：常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 立方阶 < … < 指数阶 < 阶乘   
                                           
   如：
                                           第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n1+n2+n3)=Ο(n3)。
   Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法。
   指数函数：y=ax，对数函数：y=logax，幂函数：y=xa   x为变量，a为常量