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) 的空间空间。本质上(我假设你在这里处理图表)，这意味着你为每个顶点使用了一些存储空间，为每条边使用了一些空间(也许你有一个 List<Vertex> 和一个 List<Edge> ，或者其他东西) - 很可能同时发生。

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

编辑:正如 G. Bach 指出的那样，O(v+e)永远等同于 O(max(v,e)) .我会争辩说，在某些情况下，就清晰度而言，一个或另一个更合适(一个或另一个将更好地表达实际使用的空间/时间)，但这是主观的。如果这是一门课，你的老师可能更喜欢一种符号而不是另一种符号——从类笔记中应该很明显，或者你可以问。但简而言之，O(v+e)适用于已描述的两种情况。