图灵机的时间复杂度与空间复杂度

Question

我认为图灵机的时间复杂性和空间复杂性的定义是相同的，我无法区分它们。

请帮帮我。谢谢。

Answer 1

时间复杂度是算法产生答案所需的时间长度()的量度。

空间复杂度是衡量算法在处理过程中使用了多少内存的度量。

例如，考虑计算整数1..n的和的问题。一个简单的算法会像这样工作：

procedure sum(n)
  total := 0
  for i = 1 to n
    total := total + a[n]
  return total

该算法的时间复杂度为O(n)，因为循环显然经历了n次迭代。另一方面，空间复杂度是O(1)，因为我们唯一需要的内存是total和i，它们与n无关。