yeongjae8066   4년 전

O(NM)보다 확실히 작을 것 같은데 시간복잡도 표현을 어떻게 할 수 있을 

djm03178   4년 전

O(NM)이 맞습니다. 정확히는 O(N^2 + NM)입니다.

yeongjae8066   4년 전

NM이라고 하기에는 M 간선이 10000개니까 모든 N에 대해서는 M개 방문을 못하지 않나요?

djm03178   4년 전

일단 간선은 10000개가 아니라 최대 10만 개입니다. 그리고 전체를 방문 못할 이유가 없습니다. 1 ->  2 -> 3 -> ... -> N-1 -> N -> 1 로 연결되는 사이클을 하나 만들어놓고 나머지는 아무렇게나 연결하면 어느 정점에서 탐색을 시작해도 모든 정점을 방문하고 모든 간선을 확인하게 됩니다.

djm03178   4년 전

또한 사이클을 만들 수 없다는 조건이 있더라도 시간 복잡도는 변하지 않습니다. 시간 복잡도는 점근적 표기이기 때문에 반드시 M개 전체를 사용해야 하는 것이 아니라, 매우 큰 N과 M이 주어졌을 때 총 시간이 NM에 비례하게 걸리면 되는 것입니다. 전체 탐색 과정에서 확인하는 간선 개수가 NM/2개여도 O(NM)이고, NM/9999999999개여도 O(NM)입니다.

댓글을 작성하려면 로그인해야 합니다.