인접 행렬을 분석할 때는 모든 노드를 저장하는데 사용하는 공간에 대해서 분석을 하지 않고 바로 인접행렬의 크기인 V*V에 대한 분석으로 O(V^2)라는 공간복잡도가 나온다고 나와있습니다.

인접리스트의 경우에는 모든 노드를 저장하는데 사용하는 공간을 분석하고 엣지를 저장하는데 사용하는 공간을 분석하여 평균적으로 O(V+E)라는 공간을 사용한다는 결론이 나온다고 나와있습니다.

인접 행렬의 경우에도 모든 노드를 리스트 혹은 딕셔너리에 저장하여 사용하는데 모든 노드를 저장하는데 사용하는 공간에 대해 분석을 하지 않은 것은 모든 노드를 저장하는데 사용하는 공간이 O(V)이고 인접 행렬 공간 자체로 O(V^2)라는 공간 복잡도가 나와 생략을 한 것인지 의문이 들어 질문을 올립니다.

인접리스트에서 모든 노드를 저장하는데 사용하는 공간에 대한 분석의 의미를 알고 싶습니다.

의문점:

인접 행렬에서도 모든 노드를 저장하는데 이는 인접 행렬의 공간이 상대적으로 커서 생략을 한 것인지 아니면 모든 노드를 저장하는 것이 다른 의미를 갖는 것인지
인접 행렬에서는 노드의 저장과 엣지의 저장이 독립적이여서 분석을 안한 것이고 인접 리스트의 경우는 노드의 저장과 엣지의 저장이 종속적이여서 분석을 한 것인지
실습 예제를 통해 생각해 보았을 때 인접 행렬을 구현할 때는 모든 노드를 저장하지 않았고 인접 리스트를 구현할 때는 모든 노드를 저장하지 않았는데 인접 행렬을 구현할 때는 노드의 저장이 필수불가결하지 않지만 인접 리스트를 구현할 때는 노드의 저장이 필수불가결해서인지(본 경우일 경우에는 또 다른 의문이 드는데 O(V^2)가 O(V)보다 더 큰 공간 복잡도이므로 결론이 변하지는 않지만 인접 행렬의 공간 복잡도의 분석을 할 때에 노드의 저장을 신경 써야하지 않는가에 대한 의문이 발생합니다. 왜냐하면 실무에서 인접 행렬을 사용한다는 것은 그래프를 사용하여 최단 거리를 찾는 등의 연산을 한다는 것이고 이때 필수불가결하게 노드를 리스트나 딕셔너리에 저장을 해야 한다고 생각이 들기 때문입니다.)

+)추가적으로 오타가 있는 것 같아서 제보합니다.

본문에서 인접리스트가 차지하는 공간부분에서

(수정 전)

이걸 합쳐보면 인접 리스트는 엣지를 저장하는데 O(V), 엣지를 저장하는데 O(E)을 사용하기 때문에 총 O(V+E)을 사용합니다. V와 E, 둘 중 어떤 게 더 큰지는 알 수 없기 때문에 두 알파벳 중 하나를 골라서 그거만으로 접근 표기법을 쓸 수는 없고요, 그냥 O(V+E) 만큼의 공간을 사용한다고 표현합니다.

(수정 후)

이걸 합쳐보면 인접 리스트는 노드를 저장하는데 O(V), 엣지를 저장하는데 O(E)을 사용하기 때문에 총 O(V+E)을 사용합니다. V와 E, 둘 중 어떤 게 더 큰지는 알 수 없기 때문에 두 알파벳 중 하나를 골라서 그거만으로 접근 표기법을 쓸 수는 없고요, 그냥 O(V+E) 만큼의 공간을 사용한다고 표현합니다.

오타가 발생한 것 같아 제보드립니다.