我的书指出,对于具有T(n)时间复杂度和S(n)空间复杂度的代码,以下语句成立:T(n)是omega(S(n))。我的问题是:为什么这句话成立?
我们说的是sequential算法。
然后,空间复杂度S(n)表示该算法至少以某种方式检查了S(n)个不同存储位置中的每一个。为了访问这么多的存储位置,顺序算法需要Ω(S(n))时间。