我最近学习了大O表示法,所以当我分析一些示例代码的复杂性时,我发现几乎所有示例代码的内存都更少,时间更多,所以我想反之亦然是否可能
现在我想到的一些例子是,假设输入 N* N 矩阵,并在给定索引处仅打印 1 个值,但是当我想得更多时,本质上如果我们存储 N*N 矩阵,我们必须接受输入,所以如果我有 O(N^2) 内存复杂度,O(N^2) 时间复杂度可能是必不可少的
我的想法是否正确,或者我是否缺少反例
如果你仔细想想,这很微不足道:是的。你的例子几乎是正确的,让我详细说明你的例子,并给你另一个例子来衡量。
在您的示例中,您正在考虑一些必须立即执行的代码,而不区分输入和实际查询。如果您必须加载和查询一个矩阵,很明显需要处理所有 n^2 个矩阵条目,因此我们的预处理时间和空间复杂度为
O(n^2)
,但查询本身将具有 O(1)
为时间复杂度。很明显,对于一次性代码来说它是毫无用处的,但是尝试考虑一个数据库。
在 SQL 数据库中,每个表都带有 主键
id
作为索引,并且由于这些 id
,您可以进行时间复杂度为 O(log n)
的查询,无论空间复杂度是否可以是 O(n)
或更多;因此,实际上,我们的代码的时间复杂度低于空间复杂度。