algorithm - 时间复杂度和空间复杂度的区别？

Question

我发现在大多数情况下，时间复杂度与空间复杂度相关，反之亦然。例如在数组遍历中:

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

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

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

Answer 1

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

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

  • O(1) - 常量 - 该算法使用不依赖于输入的固定(小)空间量。对于输入的每种大小，算法将占用相同(恒定)的空间量。在您的示例中就是这种情况，因为没有考虑输入，重要的是 print 命令的时间/空间。
  • O(n), O(n^2), O(log(n))... - 这些表明您可以根据输入的长度创建其他对象。例如，创建 v 的每个对象的副本，将其存储在一个数组中，然后在创建 n 时占用 O(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) 因为您没有创建额外的对象。所以，是的，一个算法可能具有不同的时间和空间复杂度，因为它们彼此不依赖。