时间复杂性与空间复杂性之间的差异
我已经看到，在大多数情况下，时间复杂性与空间复杂性有关，反之亦然。 例如在一个数组遍历中：
for i=1 to length(v) print (v[i]) endfor 在上述情况下，很容易看出algorithm在时间上的复杂性是O（n），但是对于我所看到的空间复杂度也是n（也可以用O（n）表示）？
我的问题： 一个algorithm是否有可能与空间复杂度有不同的时间复杂度？
时间和空间的复杂性并不相关。 它们被用来描述你的algorithm根据input需要多less空间/时间。
-
例如，当algorithm的空间复杂度为：
-
O(1)– 常量 – algorithm使用不依赖于input的固定（小）空间量。 对于每个input大小，algorithm将采用相同（恒定）的空间量。 在你的例子中就是这种情况，因为没有考虑到input，重要的是print命令的时间/空间。 -
O(n)，O(n^2)，O(log(n))… – 这些表示您根据input的长度创build其他对象。 例如，创build存储在数组中的每个v对象的副本，并在创buildn附加对象之后，将O(n)空间打印出来。
-
-
相反， 时间复杂度则是根据input的长度来描述algorithm消耗了多less时间。 再次：
-
O(1)– 无论input有多大，它总是需要一个固定的时间 – 例如只有一条指令。 喜欢function(list l) { print("i got a list"); } -
O(n)，O(n^2)，O(log(n))– 同样是基于input的长度。 例如function(list l) { for (node in l) { print(node); } }
-
请注意，最后两个例子都是O(1)空间，因为你不会创build任何东西。 比较他们
function(list l) { list c; for (node in l) { c.add(node); } }
由于您创build了一个新的列表，其大小取决于input的大小以线性方式，因此需要O(n)空间。
你的例子表明，时间和空间的复杂性可能是不同的。 它需要v.length * print.time来打印所有的元素。 但空间总是相同的 – O(1)因为你不创build额外的对象。 所以，是的，一个algorithm可能具有不同的时间和空间复杂度，因为它们不相互依赖。
时间和空间复杂度是计算algorithm效率的不同方面。
时间复杂性涉及到发现algorithm的计算时间如何随着input大小的变化而改变。
另一方面， 空间复杂性涉及通过改变input大小来发现algorithm需要多less（额外）空间。
要计算algorithm的时间复杂度，最好的方法是检查是否增加了input的大小，比较（或计算步骤）的数量是否也会增加，计算空间复杂度最好的办法是看到该algorithm也随input大小的变化而变化。
一个很好的例子可能是泡沫sorting 。
比方说，你试图sorting5个元素的数组。 在第一遍中，您将比较第一个元素和下一个4个元素。 在第二遍中，您将比较第二个元素和接下来的3个元素，您将继续此过程，直到完全耗尽列表。
现在如果你尝试对10个元素进行sorting会发生什么。 在这种情况下，您将开始比较第一个元素与下一个9个元素，然后第二个与下一个8个元素，依此类推。 换句话说，如果你有N个元素数组，你将通过比较第一个元素与N-1个元素，然后第二个元素与N-2个元素进行比较，依此类推。 这导致O(N^2)时间复杂度。
但是尺寸呢？ 当你sorting5元素或10元素数组时，你是否使用任何额外的缓冲区或内存空间。 你可能会说是的 ，我确实使用了一个临时variables来进行交换。 但是当你将数组的大小从5增加到10时，variables的数量是否发生了变化？不，不pipeinput大小是多less，总是使用单个variables来进行交换。 那么，这意味着input的大小与您将需要的额外空间无关，导致O(1)或恒定的空间复杂度。
现在作为一个练习，研究合并sorting的时间和空间的复杂性
首先，这个循环的空间复杂度是O(1) （当计算algorithm需要多less存储量时，通常不包括input）。
所以我的问题是，如果一个algorithm有可能从空间复杂度有不同的时间复杂度？
是的。 一般来说，algorithm的时间和空间复杂度并不相关。
有时可以牺牲另一方来增加。 这被称为时空折衷 。
是的，这绝对是可能的。 例如，sortingn实数需要O(n)空间，但O(n log n)时间。 确实，空间复杂性总是在时间复杂度上较低 ，因为初始化空间的时间包含在运行时间中。
时间和空间复杂性之间有一个很好的关系。
首先，时间是一个明显的空间消耗的约束：在时间t你不能达到超过O（t）的记忆细胞。 这通常由包含来表示
DTime(f) ⊆ DSpace(f)
其中DTime（f）和DSpace（f）是在时间（分别为空间）O（f）上由确定性图灵机识别的语言的集合。 也就是说，如果一个问题可以在时间O（f）上解决，那么它也可以在空间O（f）中求解。
不太明显的是，空间提供了时间的约束。 假设在一个大小为n的input上，你可以使用f（n）个存储单元，包括寄存器，caching和所有的东西。 在以所有 可能的 方式写入这些单元格之后，最终可能会停止计算，否则将重新input已经完成的configuration，从而开始循环。 现在，在一个二进制字母表中，f（n）个单元格可以用2 ^ f（n）个不同的方式写，这就给我们的时间上界：要么在这个界限内停止计算，要么强制终止，因为计算永远不会停止。
这通常在包含中表示
DSpace(f) ⊆ Dtime(2^(cf))
对于一些常数c。 常数c的原因是如果L在DSpace（f）中，你只知道它将在Space O（f）中被识别，而在前面的推理中，f是一个实际的边界。
上述关系被更强的版本所包含，涉及计算的非确定性模型，这是他们在教科书中经常提到的方式（参见例如Papadimitriou计算复杂性中的定理7.4）。
algorithm所需的存储空间量随着问题的大小而变化。 空间复杂度通常表示为一个数量级，例如O（N ^ 2）意味着如果问题的大小（N）增加一倍，那么将需要四倍的工作存储空间。
有时是的，他们是相关的，有时没有他们不相关，实际上，我们有时使用更多的空间，以获得更快的algorithm，如dynamic编程https://www.codechef.com/wiki/tutorial-dynamic-programmingdynamic编程使用memoization或自下而上，第一种技术使用记忆来记住重复的解决scheme，所以algorithm不需要重新计算，而只是从解决scheme列表中获得。; 自下而上的方法从小的解决scheme开始，并build立在最终的解决scheme上。 这里有两个简单的例子，一个显示时间和空间的关系，另一个显示没有关系：假设我们想要find从1到给定的n个整数的所有整数的总和：code1：
sum=0 for i=1 to n sum=sum+1 print sum
这个代码只用了6个字节，从内存i => 2，n => 2和sum => 2个字节，因此时间复杂度是O（n），而空间复杂度是O（1）
array a[n] a[1]=1 for i=2 to n a[i]=a[i-1]+i print a[n]
这段代码至less使用了来自内存的n * 2个字节，因此空间复杂度为O（n），时间复杂度也为O（n）
