时间复杂度与空间复杂度之间的差异？
我已经看到，在大多数情况下，时间复杂度与空间复杂性有关，反之亦然。 例如在数组遍历中：
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)空间。
你的例子表明时间和空间的复杂性可能不同。 它需要v.length * print.time来打印所有的元素。 但是空间总是一样的 - O(1)因为你不创建额外的对象。 所以，是的，算法可能具有不同的时间和空间复杂度，因为它们不相互依赖。
时间和空间复杂度是计算算法效率的不同方面。
时间复杂性涉及了解算法的计算时间如何随输入大小的变化而变化。
另一方面， 空间复杂度涉及通过改变输入大小来确定算法需要多少（额外）空间。
要计算算法的时间复杂度，最好的方法是检查我们是否增加了输入的大小，比较（或计算步骤）的数量是否也会增加，并计算空间复杂度，最好的办法是看到额外的内存需求该算法也随输入大小的变化而变化。
一个很好的例子可能是Bubble排序。
比方说你试图对5个元素的数组进行排序。 在第一遍中，您将比较第一个元素和下一个4个元素。 在第二步中，您将比较第二个元素和接下来的3个元素，并且您将继续此过程，直到完全耗尽列表。
现在如果您尝试对10个元素进行排序会发生什么。 在这种情况下，您将开始比较第1个元素与下一个9个元素，然后第2个与下一个8个元素进行比较，依此类推。 换句话说，如果你有N个元素数组，你将通过比较第一个元素与N-1个元素，然后第二个元素与N-2个元素等等来开始。 这导致O(N^2)时间复杂度。
但是大小呢？ 当您对5个元素或10个元素数组进行排序时，是否使用了任何其他缓冲区或内存空间。 你可能会说是的 ，我确实使用了一个临时变量来进行交换。 但是当你将数组的大小从5增加到10时，变量的数量是否发生了变化？不，无论输入的大小是多少，都将使用单个变量进行交换。 那么，这意味着输入的大小与您需要的额外空间无关，导致O(1)或恒定的空间复杂度。
现在作为练习，研究合并排序的时间和空间复杂性
首先，这个循环的空间复杂度为O(1) （当计算算法需要多少存储量时，通常不包括输入）。
所以我的问题是如果一个算法有可能与空间复杂度有不同的时间复杂度？
是的。 通常，算法的时间和空间复杂度彼此无关。
有时可以牺牲另一方来增加。 这被称为时空折衷。
链接地址: http://www.djcxy.com/p/39673.html上一篇: Differences between time complexity and space complexity?