algorithm - 时间复杂度和空间复杂度的关系

Question

时间复杂度为 O( n ) 的算法是否可以具有 O( n2 ⁾或更高的空间复杂度？

score 5 · Accepted Answer

5

空间复杂度不能超过时间复杂度，因为写入 X 个空间单位需要 Omega(X) 时间。

于 2011-08-22T17:28:58.897 回答

score 4 · Accepted Answer

看看DSPACE和DTIME组，它们表明可以在哪些时间/空间复杂度中完成什么算法，以及组之间的关系。

所有使用 O(n) 时间的算法都在 DTIME(n) 组中。
所有使用 O(n^2) 空间的算法都在 DSPACE(n^2) 组中。
因为DTIME(n) <= NTIME(n) <= DSPACE(n) < DSPACE(n^2)，所以每个 O(n) 时间的算法也是 O(n^2) 空间。

score 2 · Accepted Answer

由于所有 O(n) 函数都是平凡的 O(n ² )（参见，例如，Wikipedia on Big O notation），答案是“是的”。

score 0 · Accepted Answer

Big-O 表示法处理上限，从技术上讲，算法是 O(g(n))，对于任何和所有 g(n) 的渐近增长速度都快于 f(n)，所以如果算法是 O(n)，它必须为 O(n^2) 和 O(n^99)。

Little-o 符号处理今晚的上限，即增长速度最快的一组函数，其增长速度超过 f(n)。因此，如果 f(n) 为 o(n)，则说 f(n) 为 o(n^2) 是无效的。

编辑（回答评论）：

如果给定一个算法 A 并且被可靠地告知 A 是 O(n^2) 那么有可能 A 是 O(n) （或其他），但你必须分析 A 来找出自己。相反，如果可靠地告诉 A 是 o(n^2)，它就不可能是 O(n)。

score 0 · Accepted Answer

要回答您可能要问的问题：通常，会计是这样的，即分配给定数量的内存需要成比例的时间。为什么？好吧，实际上，在使用之前需要初始化内存。

或者，如果您假设您的所有内存都已预先初始化，那么在您的程序全部写入之后情况就不会如此了；事后仍然需要清理内存...

算法分析中使用的处理器模型其实有很多种；如果你愿意，你可以指定一个模型说“预置零内存是免费的，你不必自己清理”，这将为稀疏使用内存的算法产生不同的度量。然而，在实践中，内存分配和垃圾收集并不是免费的，所以这个指标的实际相关性有限。

5 回答 5