kimeun0   6년 전

이사이트의 온라인 강의를 듣고 있습니다. 알고리즘 중급..

해당 과정에서는 이 문제의 V가 20,000이기 때문에 priority queue를 쓰지 않고 set을 사용한 알고리즘을 가이드 하였습니다.

그런데 막상 전형적인 priority queue로도 잘 통과가 되어서.. sample set이 간단해서 그런것인지.. 혼동스러워 아시는분 계신지 질문 올립니다.

knon0501   6년 전

priority_queue를 사용한 다익스트라 알고리즘의 시간복잡도는 O(E log E)라서 충분히 통과가 됩니다.

Priority_queue를 사용하는 이유는 최솟값을 로그 시간만에 찾기 위해서인데 소스코드를 보면 set이 똑같은 역할을 하는 것 같네요.

시간복잡도를 직접 계산해 보시면 이해가 잘 될 겁니다.

graykode   5년 전

다익스트라 알고리즘은 평균적으로 ElogV의 시간복잡도를 가집니다.

힙을 사용했을 때 ElogE가 시간복잡도 인 이유는 다른 간선이 중복될수 있기 때문에 최악의 경우 ElogE인 것입니다.

Set을 사용하면 같은 간선은 중복되지 않으므로 ElogV입니다.

출처 https://namu.wiki/w/%EB%8B%A4%...

사실상 ElogE나 ElogV나 거의 차이가 없기 때문에 알고리즘 대회 수준 문제 상에서는 힙을 쓰던 Set을 쓰던 더 편한게 쓰는게 좋을거 같네요

댓글을 작성하려면 로그인해야 합니다.