题 时间复杂性和空间复杂性之间的差异?


我已经看到,在大多数情况下,时间复杂度与空间复杂性有关,反之亦然。例如,在数组遍历中:

for i=1 to length(v)
    print (v[i])
endfor

这里很容易看出算法在时间上的复杂度是O(n),但在我看来,空间复杂度也是n(也表示为O(n)?)。

我的问题: 算法是否有可能具有与空间复杂度不同的时间复杂度?


42
2017-09-08 16:41


起源


谢谢,这有助于我理解一些复杂的基本内容 - doniyor
我在哪里听到了这句话: “在有限的时间内,人们只能写入有限数量的内存,但你只需要非常有限的内存来永远迭代它” - Codor
@codor是的,一个人经常听到非常愚蠢的事情。 - Andrea Asperti
@AndreaAsperti感谢您的评论;但我在这里想念一些讽刺吗?尽管有着令人难以置信的措辞,但事实确实如此,不是吗? - Codor
@codor不,正如我在答案中解释的那样。可以检测到这种循环:你知道你在循环,因此你可以停止计算。 - Andrea Asperti


答案:


时间 和 空间 复杂性彼此无关。它们用于根据输入描述算法占用的空间/时间。

  • 例如,当算法具有时 空间 复杂性:

    • 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) 因为您不创建其他对象。所以,是的,算法可能具有不同的时间和空间复杂度,因为它们不相互依赖。


86
2017-09-12 14:23



O(1)并不意味着固定或不变,它意味着有界。例如,采用列表和气泡对第一个最多1万亿个元素进行排序的函数在时间和空间复杂度方面是O(1),但执行的比较数量从0到5e23不等。即使您将输入限制为大型列表,运行时也会从1e12到5e23不等。 - Paul Hankin
而不是将O(1)称为常量,id表示它表示占用的空间与输入大小无关。 - LoveMeow
@LoveMeow那也是假的。我记得最多100个数组的第一个元素。然后占用的空间是O(1),但不与输入大小无关。 - John Dvorak
空间和时间相结合....这个答案开始是错误的 - Aviad
同意Aviad,这个答案是错误的。时间和空间的复杂性是相互关联的。 - Andrea Asperti


时间和空间复杂度是计算算法效率的不同方面。

时间复杂 讨论了如何计算时间   算法随输入大小的变化而变化。

另一方面, 空间复杂性 处理找出多少   算法需要(额外)空间,而改变   输入大小。

要计算算法的时间复杂度,最好的方法是检查我们是否增加输入的大小,比较(或计算步骤)的数量是否也会增加并计算空间复杂度,最好的办法是看到额外的内存需求。算法也随着输入大小的变化而变化。

一个很好的例子可能是 冒泡排序

假设您尝试对5个元素进行排序。 在第一遍中,您将比较第一个元素和下一个4个元素。在第二遍中,您将比较第二个元素和接下来的3个元素,您将继续此过程,直到您完全耗尽列表。

现在,如果您尝试对10个元素进行排序,会发生什么。在这种情况下,您将首先比较第一个元素与下一个9个元素,然后是第二个元素与下一个8个元素,依此类推。换句话说,如果你有N个元素数组,你将首先将第一个元素与N-1个元素进行比较,然后将第二个元素与N-2个元素进行比较,依此类推。这导致了 O(N^2) 时间复杂。

但是大小呢。当你排序5个元素或10个元素数组时,你使用任何额外的缓冲区或内存空间。你可能会说 ,我确实使用临时变量进行交换。但是,当您将数组的大小从5增加到10时,变量的数量是否会发生变化。不,无论输入的大小是多少,您始终都会使用单个变量来进行交换。嗯,这意味着输入的大小与您需要的额外空间无关 O(1) 或恒定的空间复杂性。

现在作为练习,研究时间和空间的复杂性 合并排序


46
2017-09-09 20:29



@LoveMeow感谢您的投入。我更新了链接。 - Prateek


首先,这个循环的空间复杂性是 O(1) (在计算算法需要多少存储空间时,通常不包括输入)。

所以我的问题是,算法是否可能具有与空间复杂度不同的时间复杂度?

是的。通常,算法的时间和空间复杂度彼此无关。

有时候可以牺牲另一个来增加一个。这就是所谓的 时空权衡


4
2017-09-08 16:45



你能分享一些例子吗? @NPE - Little
一个常见的假设是空间不能比时间更糟糕,因为启动分配内存的工作随着分配大小而增长。 - smossen
@smossen:很好的观察! - NPE
@smossen如何把它放在答案中? - TooTone


是的,这绝对是可能的。例如,排序 n 实数需要 O(n) 空间,但是 O(n log n) 时间。确实,空间复杂性总是如此 下界 时间复杂度,因为初始化空间的时间包含在运行时间中。


4
2017-09-09 22:11



通常空间复杂度描述算法所需的额外空间,并且可以使用O(1)(附加)空间进行排序(因此它不需要O(n)空间)。而且我认为你必须在这里使用空间复杂性的“额外空间”定义,否则你会说排序数组的二进制搜索需要O(n)空间并且在O(log n)时间内运行时与你的声明相矛盾时间复杂性总是占据空间复杂性。 - Paul Hankin


时间和空间复杂性之间存在众所周知的关系。

首先,时间与空间消耗明显相关:时间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的复杂性)。


4
2018-02-21 08:46



但如果你实际上不知道你访问了多少个州,你如何强制终止$ 2 ^ f(n)$? - Guillermo Mosse
@SenorBilly实际上,您不需要计算,也不需要强制终止。您 知道 机器将在该时间范围内停止,因为否则它将处于循环中(并且它不能循环,否则空间消耗将是未定义的,因为它是在计算结束时测量的)。 - Andrea Asperti


有时是的,他们是相关的,有时他们没有关联, 实际上,我们有时会使用更多空间来获得更快的算法,就像动态编程 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)


1
2018-05-06 19:48





算法所需的存储空间量随着解决问题的大小而变化的方式。空间复杂度通常表示为一个数量级,例如O(N ^ 2)意味着如果问题(N)的大小加倍,那么将需要四倍的工作存储。


0
2017-10-06 06:35