algorithm - 算法符号确认分析

Question

我会继续提到这是家庭作业，但我不是在寻求典型的家庭作业帮助。我只是想确认问题的措辞。问题表明我的算法应该与图中的顶点数成线性关系。我从来没有见过这种措辞，只是说我的运行时间应该是 O(|V|) 吗？如果是这样，我想我有我的解决方案。

Answer 1

在算法分析中，算法根据输入大小按效率进行分类。

O(|V|)意味着您的算法必须检查或“触摸”图中的每个顶点。所以是的，顶点数的线性意味着O(|V|)。

供参考，在 Big O、Ɵ或Ω; 两条竖线表示的数量。在某些证明中，它们也用于表示长度。