时间复杂度和空间复杂度的关系
时间复杂度为 O(n) 的算法的空间复杂度可以为 O(n2) 或更高吗？
Can an algorithm having a time complexity of O(n) have a space complexity of O(n2) or more than that?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
空间复杂度不能大于时间复杂度，因为写入 X 个单位的空间需要 Omega(X) 时间。
The space complexity cannot be more than the time complexity because writing X units of space takes Omega(X) time.
看看 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)。have a look at the DSPACE and DTIME groups, which indicate what algorithm can be done in which time/space complexity, and the relationship between groups.
all algorithms that use O(n) time are in the group DTIME(n).
all algorithms that use O(n^2) space, are in the group DSPACE(n^2).
since
DTIME(n) <= NTIME(n) <= DSPACE(n) < DSPACE(n^2), so every algorithm that is O(n) time, is also O(n^2) space.由于所有 O(n) 函数都是普通的 O(n2) （参见，例如 关于大 O 表示法的维基百科），答案是“是”。
Since all O(n) functions are trivially O(n2) (see, e.g., Wikipedia on Big O notation), the answer is "yes."
Big-O 表示法涉及上限，从技术上讲，对于任何和所有渐近增长速度快于 f(n) 的 g(n)，算法的复杂度为 O( g(n) )，因此如果算法为 O(n)，则它必须为 O(n^2) 和 O(n^99)。
Little-o 表示法涉及今晚的上限，即增长速度最快的函数集，其增长速度快于 f(n)。因此，说 f(n) 是 o(n^2) 是无效的，当且仅当它是 o(n) 时。
编辑（回答评论）：
如果给定一个算法 A 并被可靠地告知 A 是 O(n^2) 那么 A 可能是 O(n) （或其他），但你必须分析 A 才能找到自己出来。相反，如果可靠地告诉 A 是 o(n^2)，那么它不可能是 O(n)。
Big-O notation deals in upper bounds, technically speaking an algorithm is O( g(n) ) for any and all g(n) that grow asympoticaly faster than f(n), so if an algorithm is O(n) it must be O(n^2) and O(n^99).
Little-o notation deals in tonight upper bounds, i.e the least fastest growing set of functions which grow faster than f(n). Therefore its not valid to say f(n) is o(n^2) iff it is o(n).
Edit (to answer comment):
If given an algorithm A and being told reliably that A is O(n^2) then there is the possibility that A is O(n) (or whatever) but you would have to analyse A to find out yourself. Conversely, if reliably told A was o(n^2) it cannot be O(n).
为了回答您可能想问的问题：通常，计算是分配给定数量的内存需要成比例的时间。为什么？好吧，实际上来说，在使用内存之前需要先初始化它。
或者，如果您假设所有内存都已预先初始化，那么在您的程序对其进行全部写入后，情况就不会如此；之后仍然需要清理内存...
算法分析中使用的处理器模型实际上有很多种；如果您愿意，您可以指定一个模型，表示“预清零内存是免费的，并且您不必自己清理”，这将为稀疏使用内存的算法产生不同的指标。然而，实际上，内存分配和垃圾收集并不是免费的，因此该指标的实际意义有限。
To answer the question you probably meant to ask: generally, the accounting is such that allocating a given amount of memory takes a proportional amount of time. Why? well, practically speaking, something needs to initialize the memory before you use it.
Alternately, if you assume that all your memory comes pre-initialized, then this will not be the case after your procedure writes all over it; something would still need to clean up the memory afterwards...
There are actually a variety of processor models used in algorithm analysis; if you wanted, you could specify a model that says "pre-zeroed memory is free, and you don't have to clean up after yourself", which would yield a different metric for algorithms that use memory sparsely. However, in practice memory allocation and garbage collection are not free, so this metric would have limited practical relevance.