图的时间复杂度

Question

我正在研究图的时间复杂度。我不明白的是，为什么O|V|^2|E|)的时间复杂度优于O(|E|^2|V|)。它们中的一个是^2，为什么一个比另一个好？

Answer 1

在实践中，图的边通常比顶点多。考虑一下这不是真的情况:一个图，其中|E| < |V|。例如，这样的图可以是简单的路径，其中顶点以链的形式彼此连接。在这种情况下，您可能会问自己是否需要将此结构表示为图形。

在更复杂的图中，您会发现边比顶点多。在另一个极端，一个完全连通的图有O(|V|^2)边。对于这样的图，您可以将O(|V|^4)算法与O(|V|^5)算法进行比较。

因此，尽管不是所有的图都是这样，但与O(|E|^2|V|)算法相比，您在实践中可能会遇到的那些图将从O(|V|^2|E|)算法中获得更多的好处。