그래프 문제를 해결하는 알고리즘의 실행 시간

Question

사람들이 그래프 문제를 해결하기위한 알고리즘에 대해 이야기 할 때, 실행 시간에 고려되는 입력 - 정점 수, 에지 수 또는 둘 다? 다르게 말하면, O(|V|), O(|E|) 및 O(|V||E|)은 모두 그래프 알고리즘의 유효한 다항식 실행 시간 일 수 있습니까? |V| 또는 |E| 중 하나가 다른 것보다 큰 경우 중요합니까?

Answer 1

두 알고리즘은 알고리즘에 따라 적절할 수 있습니다. 중요한 영향을 미치는 입력 만이 복잡성을 계산하는 데 사용됩니다.

알려진 그래프 알고리즘의 몇 가지 예인 http://bigocheatsheet.com/에 대한 그의 링크를 살펴볼 수 있습니다. 때로는 |V| 또는 |E| 중 하나가 표시되는 경우가 있습니다.