1
Floyd-Warshall 알고리즘에 저장 장치 
이있는 이유는 무엇입니까? 링크드리스트가 N × N 매트릭스와 대조적으로 사용된다면 그것보다 작지 않을까요?Floyd-Warshall 알고리즘의 O (n^2) 저장 장치에 관한 정보
A
답변
1
링크 된 목록의 최악의 경우 크기는 여전히 O(n^2) (필자는 사용자가 사용하기를 제안하는 방법을 잘 모르겠다)이지만 조회 비용은 점근 적 복잡성을 변경하기에 충분히 비쌉니다. 전체 알고리즘 (링크 된 목록에 대한 연산은 알려진 크기의 행렬에 대한 연산과 동일한 복잡성을 갖지 않습니다).
링크 된 목록에 대한 내 제안은 각 노드가 그래프의 정점을 대표하게 될 것입니다. 이 방법을 사용하면 v^2 번과 반대되는 그래프의 v + e 번만 정점의 수를 저장하게됩니다. 내 알고리즘 교수는 N × N 행렬보다 연결된 목록으로 그래프를 저장하는 것이 더 좋다고 말했지만, 내 견해는 조회 비용이 절약 된 공간에 비해 너무 비싸다는 것이 었습니다. 그녀의 주장은 10 억 개의 꼭지점이 있다면 절약 된 공간이 그만한 가치가 있다는 것입니다. 나는 이것이 사실이 아니라고 생각하고 있습니다. –
연결된 목록은 그래프를 저장하는 엉뚱한 방법입니다. 인접성 목록을 저장한다는 의미입니까? 그것은 다소 다릅니다. 최악의 경우'(n-1)^2 '값이되는 모든 가중치를 저장해야하는 위치가 여전히 필요하다는 것을 명심하십시오. – Gian