1
우리는 다중 도트에 대한 인접성리스트 G = (V, E)와 동등한 (간단한) 무 방향 그래프의 인접 목록을 계산하기 위해 O (V + E) 알고리즘을 찾아야합니다. multigraph에 대한 인접 목록이 주어지면 O (| V | + | E |) 시간에 해당하는 (단순한) 무 방향성 그래프에 대한 인접성 목록을 계산합니다.
는 I (이것은 문제 부 그러므로 내 재 게시의 일부) 다른 게시물 다음 용액을 발견"[H] 크기의 배열 AVING |왔다 정점을 표시하도록 | V를 adj [u]에서 적어도 한 번 이상 발생하여 중복을 방지합니다. 배열은 각 adj [u]를 통과하기 전에 재설정됩니다. "
내 무지를 용서해주세요. 그러나 이것이 어떻게 O (| V | + | E |)인지 잘 모르겠습니다. 길이를 다시 설정하는 비용은 얼마입니까? | V | 배열 | V | 타임스?
감사합니다.
귀하가 고려하는 사항에 따라 달라질 수 있습니다. 신선한 메모리를 할당하고 이전 값을 지우는 것에서부터 모든 값을 0으로 덮어 쓰는 것부터 단순히 오래된 값을 무시하고 0에서 쓰기 시작하는 것일 수 있습니다. 인용문은 이것을 판단 할 컨텍스트가 없습니다. 그리고 런타임 복잡성의 주요 문제점은 ** ** 무엇이 측정되는지에 달려 있다는 것입니다 (일반적으로 가장 비싼 작업이지만 여기서는 꽤 모호합니다). – Paul
안녕하세요 @Paul. 복잡성 요구 사항을 충족시킬 수있는 '재설정'에 대한 해석을 생각해 볼 수 있습니까? 저는 이전의 값을 그냥 무시할 수 있다고 생각하지 않습니다 ... – tarski
설정되어있는 정점 목록을 유지하면 배열 위치 만 재설정 할 수 있습니다. 따라서 세트의 비용이 너무 많이 들지 않으므로 다음과 같이 처리 할 수 있습니다. 세트 비용에 대한 일정한 요소. 또 다른 방법은 배열에 정수 값으로 설정하여 위치를 설정하고 각 통과에서 해당 정수 값을 증가시키고 현재 값보다 작은 값으로 설정된 위치를 설정 해제로 처리하는 것입니다. – mcdowella