算法的空间复杂度于时间复杂度的关系

算机在完成一个任务的时候有两个指标，时间和所有内存（也就是空间）。这两者是负相关的。也就是说，当你设计一个特定程序时，你可以选择使用更多的内存，这样可以达到提高程序运行速度的目的，也就是减少程序运行时间。另一方面，你也可以选择使用较少的内存，这样可以节省内存但同时程序运行速度会变慢，也就是说程序运行要花费更多的时间。简言之，算法中只有两种策略，要么以时间换空间，要么以空间换时间。
直接回答问题就是空间复杂度高的算法其时间复杂度低，反之亦然。

（7）下列叙述中正确的是________。

　A）一个算法的空间复杂度大，则其时间复杂度也必定大

　B）一个算法的空间复杂度大，则其时间复杂度必定小

　C）一个算法的时间复杂度大，则其空间复杂度必定小

　D）上述三种说法都不对

答案：

06—10CDBBA

选D

回答人的补充 2010-09-09 11:44

有“必定”的话不对。因为对一些特殊情况存在特例有高的时空复杂度或同时为低的时空复杂度。但对一般情况下给定存储空间如给定65535K的内存但不限定时间时，就存在时间空间的负相关关系。对于既不限定时间，也不限定空间的程序，算法的时间复杂度和空间复杂度可以同时很大，也可以同时很小。如T(n)=O(n)且S(n)=O(1)的情况比如一个for(i=0;i<N;i++)，若循环体中为一个与问题规模无关的变量变化，则其S(n)=O(1)，而T(n)=O(n)是随着N的变化而变化的，这时可以说时间复杂度较小而空间复杂度很小。