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