我已经看到,在大多数情况下,时间复杂度与空间复杂性有关,反之亦然。例如,在数组遍历中:
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)的大小加倍,那么将需要四倍的工作存储。