空间复杂度始终是时间复杂度的下限[关闭]

问题描述 投票:-3回答:1

我的书指出,对于具有T(n)时间复杂度和S(n)空间复杂度的代码,以下语句成立:T(n)是omega(S(n))。我的问题是:为什么这句话成立?

algorithm time-complexity analysis
1个回答
4
投票

我们说的是sequential算法。

然后,空间复杂度S(n)表示该算法至少以某种方式检查了S(n)个不同存储位置中的每一个。为了访问这么多的存储位置,顺序算法需要Ω(S(n))时间。

© www.soinside.com 2019 - 2024. All rights reserved.