algorithm - 空间复杂度总是时间复杂度的下界

Question

我的书指出，对于具有 T(n) 时间复杂度和 S(n) 空间复杂度的代码，以下语句成立：T(n) 是 omega(S(n))。我的问题是：为什么这个说法成立？

标签： algorithmtime-complexityanalysis

Answer 1

我们说的是顺序算法。

那么空间复杂度 S(n) 意味着该算法以某种方式检查每个 S(n) 个不同的内存位置至少一次。为了访问这么多内存位置，顺序算法需要 Ω(S(n)) 时间。