0
무향 그래프의 경우 인접리스트 표현에 2E 에지가 있기 때문에 왜 메모리 요구 사항이 유향 그래프와 동일한가?무향 그래프의 경우 인접성 목록 표현에 필요한 메모리가 θ (V + 2E)가 아닌 θ (V + E) 인 이유는 무엇입니까?
A
답변
0
쎄타 (V + E) = 쎄타 (V + 2E) 2는 상수이므로 big-O notation에서 차이가 없기 때문에.
+0
큰 O에서 차이를 만들지는 않지만 세타가 더 엄격한 경계이기 때문에 세타는 어떨까요? –
+0
정의를보십시오. Theta (V + E)는 Big-O (V + E)와 Omega (V + E)에 있음을 의미합니다. 그래서 주어진 고정 된 n0와 상수에 대해 그것은 Big-O에 있습니다. 우리의 경우 상수는 2입니다. 다른 상수에 대해서는 1로 놓으십시오. 오메가에 있습니다. – gue
각 가장자리를 한 번만 저장하면됩니다. 가장자리가 'i, j'이고 'i