时间复杂性和空间复杂性之间的差异？

Question

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

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

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

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

Answer 1

在时间和空间复杂度不彼此相关.它们用于根据输入描述算法占用的空间/时间.

• 例如,当算法的空间复杂度为:

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

Answer 2

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

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

另一方面,空间复杂性涉及通过改变输入大小来找出算法需要多少(额外)空间.

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

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

让我们说你试图对5个元素的数组进行排序.在第一遍中,您将比较第一个元素和下一个4个元素.在第二遍中,您将比较第二个元素和接下来的3个元素,您将继续此过程,直到您完全耗尽列表.

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

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

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

Answer 3

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

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

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

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

Answer 4

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

首先，时间显然是空间消耗的约束：在时间t中，您到达的存储单元不能超过O（t）个。这通常通过包含来表示

                            DTime(f) ? DSpace(f)

其中DTime（f）和DSpace（f）是确定性图灵机在时间（分别为空间）O（f）中可识别的语言集。也就是说，如果可以在时间O（f）中解决问题，那么也可以在空间O（f）中解决问题。

事实证明，空间提供了时间的约束。假设在大小为n的输入上，您可以使用f（n）个存储单元，其中包括寄存器，缓存和所有内容。在以所有 可能的 方式编写完这些单元之后，您最终可能会停止计算，因为否则您将重新输入已经经历的配置，从而开始循环。现在，在二进制字母上，可以用2 ^ f（n）种不同的方式来写f（n）个单元，这给了我们时间上界：要么计算将在此边界内停止，要么您可以强制终止，因为计算永远不会停止。

这通常表示为

                          DSpace(f) ? Dtime(2^(cf))

对于某些常数c。常数c的原因是，如果L在DSpace（f）中，则您仅知道它将在空间O（f）中被识别，而在前面的推理中，f是实际边界。

上述关系被包含非确定性计算模型的更强版本所包含，这就是它们在教科书中经常陈述的方式（例如，参见Papadimitriou的“计算复杂性”中的定理7.4）。

Answer 5

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