pho*_*nix 1 algorithm graph-algorithm
时间复杂度，O(v+e)很明显它类似于在程序中单独运行的 2 个循环（e 次和 v 次）。
但是，当同样涉及空间复杂性时，我感到困惑。
是不是先分配O(v)空间，然后释放空间，再分配O(e)空间？
谢谢！
当您处理时间复杂度时，加法 ( O(v+e)) 意味着两件事按顺序发生。当你转向空间复杂性时，+符号应该在空间上下文中使用，而不是在时间上下文中。
O(v+e)空间相当于使用O(v)+O(e)空间。本质上（我假设您在这里处理图形），这意味着您为每个顶点使用了一些存储空间，为每个边使用了一些空间（也许您有 aList<Vertex>和 a List<Edge>，或者其他东西）-很可能全部在同时。
在您分配O(v)内存、释放内存然后分配O(e)内存的示例中，您O(max(v,e))随时都在使用空间。
编辑：正如 G. Bach 指出的那样，O(v+e)将始终等同于O(max(v,e)). 我认为在某些情况下，就清晰度而言，其中一个更合适（一个或另一个将更好地表达实际使用的空间/时间），但这是主观的。如果这是针对课堂的，您的教师可能更喜欢一种符号而不是另一种 - 从课堂笔记中应该很明显，或者您可以询问。但简而言之，O(v+e)适用于已描述的两种情况。