인프런 커뮤니티 질문&답변
작성한 질문수
4-5 그래프 강의 내용에 대해 질문드립니다.
해결된 질문
작성
·
62
0
안녕하세요!
'4-5 그래프' 강의 내용 중에 '인접 리스트'를 사용해 그래프를 표현하는 경우 공간복잡도가 최악의 경우에도 O(N)이라고 설명을 해주셨는데요!
그래프의 모든 노드가 다른 모든 노드에 연결되어있는 경우라면 딕셔너리 안에 N개의 키와 각각의 키에 크기 N-1의 1차원 배열이 들어가게 되니, 결국 N*(N-1) 만큼이 공간을 차지하여 최악의 경우 2차원 배열과 동일하게 O(N^2)의 공간복잡도를 가지게 되는 것은 아닌가 하는 생각이 들었는데요,
인접 리스트를 사용할 때 최악의 경우 어떻게 O(N)의 공간복잡도가 나오게 되는지 궁금합니다!
그리고, 일반적인 경우에는 모든 노드가 연결되어 있지는 않겠지만, 항상 이러한 최악의 경우도 고려하면서 문제를 풀어야 할지도 궁금합니다!
답변 2
0
안녕하세요 chohk 님!! 좋은 질문 감사합니다!!
먼저, chock 님의 말씀이 정확합니다!! 인접 리스트의 공간복잡도를 올바르게 분석해보겠습니다.
최악의 경우(완전 그래프)
N개의 노드가 각각 다른 모든 노드와 연결된 경우
각 노드는 N-1개의 간선 정보를 저장
따라서 총 공간복잡도는 O(N * (N-1)) = O(N^2)
일반적인 경우
간선의 수 E가 노드 수 N보다 적은 경우(E < N^2)
공간복잡도는 O(N + E)
제 강의에서 인접 리스트의 공간복잡도를 O(N)으로 설명한 것은 "E 의 개수가 매우 작거나 비례하는 그래프의 형태" 임을 상정하고 표현했던 것 같습니다. 정확히는 O(N + E)로 표현하는 것이 맞습니다. 인접행렬과 인접리스트의 공간복잡도를 비교하는 상황이었기에, 간선이 별로 존재하지 않는 경우라는 전제가 깔려있어서 이와 같이 설명을 했던 것 같습니다.
그럼에도 불구하고 chohk 님이 말씀해주신것처럼 최악의 경우에서는 O(N^2) 도 가능하다는 것을 고려하는 것이 맞다고 생각합니다 이 부분은 교재에 반영을 해두도록 하겠습니다 좋은 피드백 너무너무 감사드립니다!!
추가적으로 말씀해주신 내용은 문제의 입력값 범위에 따라 결정해보시면 좋을 것 같습니다
예를 들어 노드의 개수의 범위는 0 <= x <= 100,000 이다.
간선의 개수의 범위는 0 <= y <= 100 이다.
와 같은 입력값일 경우에는 N+E 의 범위가 N^2 까지는 갈 수 없겠다. O(N) 이라고 보고 풀면 되겠다 라고 생각해주시면 좋을 것 같습니다.
0
안녕하세요, 인프런 AI 인턴입니다.
chohk님께서 주신 질문에 대해 답변드리겠습니다.
그래프를 인접 리스트로 표현할 때의 공간 복잡도에 대한 이해가 혼란스러울 수 있습니다. 인접 리스트는 노드 수 N과 에지 수 E에 따라 공간을 사용합니다. 일반적으로 인접 리스트의 공간 복잡도는 O(N + E)입니다. 이는 N개의 노드에 어느 노드가 다른 노드와 연결되어 있는지를 기록하기 때문입니다.
chohk님께서 말씀하신 최악의 경우, 모든 노드가 모든 다른 노드와 연결되어 있는, 즉 완전 그래프인 경우를 생각해 보면, 노드 수는 N개, 에지는 N(N-1)/2개가 됩니다. 따라서 이 경우의 공간 복잡도는 O(N + N(N-1))로 O(N^2)가 됩니다. 이는 인접 리스트의 공간 복잡도가 아니라 에지 수에 종속적이라는 사실을 보여줍니다.
따라서 그래프가 희소할 경우(대부분의 노드가 연결되지 않은 경우), 인접 리스트는 인접 행렬보다 훨씬 효율적인 공간 사용을 하게 됩니다. 그러나 완전 그래프와 같이 모든 노드가 모든 다른 노드에 이어져 있는 경우의 최악의 공간 사용에서는 인접 리스트도 인접 행렬과 유사한 O(N^2)의 공간 복잡도를 가질 수 있습니다.
최악의 상황까지 항상 고려해야 하는지는 문제의 특성에 따라 다릅니다. 대부분의 경우, 특히 코딩 테스트에서는 평균적인 경우를 더욱 많이 다루며, 적절히 사용될 수 있는 자료 구조를 선택하는 것이 중요합니다.
추가적으로 참고할 수 있는 Spring Boot의 Neo4j 관련 문서도 있습니다.
질문에 도움이 되셨기를 바라고, 추가적인 궁금증이 있다면 언제든지 문의 주세요!