멀티 그래픽 및 인접 목록

Question

멀티 그래픽으로 표현할 수있는 문제가 있습니다. 이 그래프를 내부적으로 표현하기 위해, 나는 행렬을 생각하고있다. 나는 정점에 대한 모서리의 수를 계산하기를 원하기 때문에 매트릭스의 아이디어를 좋아합니다. 이것은 O (n) 시간 일 것입니다. 왜냐하면 올바른 계산을 반복하면 시간 복잡도가 그래프의 정점 양에 선형이 될 것이기 때문입니다. 그러나 공간의 복잡성에 대해서도 생각하고 있습니다. 이 그래프가 커지면 많은 공간이 낭비 될 수 있습니다. 이것은 내가 인접 목록을 사용하게 만든다. 이것은 공간 복잡성을 줄일 수 있지만 내 시간 복잡성이 증가한 것처럼 들립니다. 특정 꼭지점의 가장자리 수를 결정하려면 시간 복잡도를 어떻게 표현해야합니까? 나는이 연산이 O (n)이 될 수 있도록 연산이 꼭 꼭지점을 찾는 것이지만, 또한 O (n) 일 수있는 모서리의 목록을 스캔해야한다는 것을 안다. 이것이이 연산의 시간 복잡도가 O (n^2)라는 것을 의미합니까?

편집 :

내가 해시 테이블을 사용한다면, 최초의 조작이 O (1) 그래서 그 정점에 대한 모서리의 수를 찾을 수 내 작업을 의미 하는가 될 생각은 O (N)?

Answer 1

O (| e |), | e | O (| v | ** 2)가 될 수 있지만 행렬이 희박하므로 인접 목록을 사용하고 싶습니다. < < | v | 그래서 O (| e |)라고 말하는 것이 낫습니다.