algorithm - O(V+E) 空间复杂度是什么意思？

Question

时间复杂度，O(v+e)很明显它类似于在一个程序中分别运行 2 个循环（e 次和 v 次）。

但是，当涉及到空间复杂性时，我感到很困惑。

是不是先分配O(v)空间然后释放它然后分配O(e)空间？

谢谢！

Answer 1

当您处理时间复杂度时，加法 ( O(v+e)) 意味着两件事是按顺序发生的。当你转向空间复杂性时，+符号应该在空间而不是时间的背景下使用。

O(v+e)空间相当于使用O(v)+O(e)空间。本质上（我假设您在这里处理图形），这意味着您正在为每个顶点使用一些存储空间，为每个边使用一些空间（也许您有 aList<Vertex>和 aList<Edge>或其他东西） - 很可能都在同时。

在分配O(v)内存、释放内存、然后分配O(e)内存的示例中，您O(max(v,e))随时都在使用空间。

编辑：正如 G. Bach 指出的，O(v+e)将始终等同于O(max(v,e)). 我会争辩说，在某些情况下，其中一个或另一个在清晰度方面更合适（一个或另一个将更好地表达实际使用的空间/时间），但这是主观的。如果这是针对课程的，您的讲师可能更喜欢一种符号而不是另一种 - 从课堂笔记中应该很明显，或者您可以询问。但简而言之，O(v+e)适用于已描述的两种情况。