인접리스트 시간 복잡도가 잘 이해가 가지 않습니다.

작성한 질문수 1

1

안녕하세요 창욱님 ㅎㅎ

vector<int> v1[V] 만큼의 배열을 생성하고 나서, 각 배열에 연결할 정점들을 다 카운트 했을 때 E개라서 공간복잡도가 O(V + E) 이라고 이해해도 될까요?

E = E * push_back(i);

와 같은 코드로 이해했습니다.

>> 음.. 맞는데 조금은 틀린 부분이 있는데요. 다시 설명을 드려볼게요. ㅎㅎ

자, 이런 경우의 수를 들어볼게요.

자 앞의 그림을 봤을 때

v[1].push_back(2)

v[1].push_back(2)

v[1].push_back(2)

이런 꼴이 되겠죠?

먼저 하나의 정점에 여러개의 간선이 들어갈 수 있습니다.

자 여기서

v[1].push_back(2)가 상징하는 바는.

1이라는 정점에 2라는 정점을 잇는 간선을 추가한다가 됩니다.

E * push_back(i);

이것 보다는.

V . push_back(V)가 맞는 표현입니다.

정점에 정점을 추가하는 것이죠.

저 앞의 그림의 공간복잡도는 어떻게 될까요?

먼저 저 정점 2개죠? V입니다.

그리고 저 정점을 잇는 간선 3개, E죠?

그래서 V + E가 되는 것입니다.

즉

vector<int> v1[V] 만큼의 배열을 생성하고 나서, 각 배열에 연결할 정점들을 다 카운트 했을 때 E개라서 공간복잡도가 O(V + E) 이라고 이해해도 될까요?

가 아니라.

정점의 갯수만큼 vector<int> v1[V] 만큼의 배열을 생성하고 나서, 각 정점들을 잇는 간선들을 다 카운트 했을 때 총 E개라서 공간복잡도가 O(V + E) 이가 됩니다.

가 맞는 표현입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.