How does

2018-06-14 00:27:41

I am looking at code to find complexity of deep first search (DFS). How does O(|V| + |E|) differ from O(V+E). What is the meaning of |·| around V and E? Does it mean the "sum of all vertices" is represented as |V| ?

V and E are a sets. So O(E) would be undefined. |·| gives you the number of elements in the set, it's called cardinality in Maths. For a graph G = (V,E) |E| is the number of edges, |V| is the number of vertices.

When people write O(V+E) they actually mean O(|V| + |E|) and most readers will understand it that way, because it is the only plausible explanation. Still it is unclean and I would not use it myself.

|V| typically means the cardinality (number of elements) in V. So O(|V| + |E|) means "on the order of the number of elements in V plus the number of elements in E."

链接地址: http://www.djcxy.com/p/39924.html

上一篇: 算法随机产生一个美学

下一篇: 如何