58

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

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

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

我的问题：算法的时间复杂度是否可能与空间复杂度不同？

4

7 回答 7

109

时间复杂度和空间复杂度彼此无关。它们用于描述您的算法基于输入需要多少空间/时间。

  • 例如，当算法的空间复杂度为：

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

于 2013-09-12T14:23:04.487 回答
62

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

时间复杂度涉及找出算法的计算时间如何随着输入大小的变化而变化。

另一方面，空间复杂度处理的是随着输入大小的变化，算法需要多少（额外）空间。

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

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

假设您尝试对包含 5 个元素的数组进行排序。在第一遍中，您将比较第一个元素与接下来的 4 个元素。在第二遍中，您将比较第二个元素与接下来的 3 个元素，您将继续此过程，直到您完全用完列表。

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

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

现在作为一个练习，研究归并排序的时间和空间复杂度

于 2013-09-09T20:29:19.957 回答
7

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

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

是的。一般来说，算法的时间复杂度和空间复杂度是不相关的。

有时可以以牺牲另一个为代价来增加一个。这称为时空权衡。

于 2013-09-08T16:45:42.960 回答
7

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

首先，时间显然与空间消耗有关：在时间 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) 中，你只知道它会在 Space O(f) 中被识别，而在前面的推理中，f 是一个实际的界限。

上述关系包含在更强的版本中，涉及非确定性计算模型，这是教科书中经常陈述的方式（参见 Papadimitriou 的 Computational Complexity 中的定理 7.4）。

于 2017-02-21T08:46:45.410 回答
5

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

于 2013-09-09T22:11:52.590 回答
1

有时是的，它们是相关的，有时不是，它们不相关，实际上我们有时会使用更多空间来获得更快的算法，如动态编程https://www.codechef.com/wiki/tutorial-dynamic-programming 动态编程使用记忆或自下而上，第一种技术使用内存来记住重复的解决方案，因此算法不需要重新计算它，而只需从解决方案列表中获取它们。自下而上的方法从小的解决方案开始，并在此基础上达到最终的解决方案。这里有两个简单的例子，一个显示时间和空间之间的关系，另一个显示没有关系：假设我们要找到从 1 到给定 n 整数的所有整数的总和：code1：

sum=0
for i=1 to n
   sum=sum+1
print sum

此代码仅使用内存 i=>2,n=>2 和 sum=>2 字节的 6 个字节，因此时间复杂度为 O(n)，而空间复杂度为 O(1) code2：

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)

于 2016-05-06T19:48:43.533 回答
0

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

于 2015-10-06T06:35:23.223 回答