다익스트라 우선순위 큐 사용시 시간복잡도 ElogV에 대한 질문이 있습니다.

  • lsh9034
    lsh9034

    아 문제에 대한 질문은 아니구요... 제가 공부를 하다가 잘 이해가 되지 않는데 물어볼 곳이 정말 없더라구요.. 여기에 알고리즘을 다 씹어먹는다는 분들이 많다고 들어 질문을 하려고 합니다. 우선순위 큐를 쓸 때 시간복잡도가 ElogV가 된다고 하는데요. 제가 그림판에 그려가면서 최악을 생각을 해보았는데 우선순위 큐에서 최대 E번을 팝하고 거기서 다시 인접한 부분들을 탐색하기 때문에 logV뒤에 E가 왜 붙는지는 알겠습니다. 근데 정점을 정하고 인접한 간선을 탐색해야하잖아요. 인접행렬말고 벡터나 리스트로 짜도 최대 V번 돌게 되어있고 최악의 경우 V번 돌 때마다 우선순위 큐에 넣는다고 가정하면 직관적으로 최악을 생각해보면 logE라고 생각됩니다. 그렇게 되면 E*V*logE인데 logE가 logV^2가 비스무리 해서 logV가 되는건 알고 있습니다. 그래도 중간에 V가 곱해져 있어서 ElogV와는 다르게 되더라구요.. 이 부분에 대한 명쾌한 답변 부탁드립니다. 제가 그렸던 그림판 첨부해보겠습니다.
    그림


    7년 전
4개의 댓글이 있습니다.
  • lsh9034
    lsh9034

    이거 그림 어떻게 올리는지 잘 모르겠어요...


    7년 전 link
  • hyunhwan
    hyunhwan

    https://imgur.com 와 같은 이미지 업로드 사이트를 이용해 올리신 다음 링크를 걸거나 markdown 문법을 이용해서 아래 첨부하시면 됩니다.


    7년 전 link
  • wookayin
    wookayin

    근데 정점을 정하고 인접한 간선을 탐색해야하잖아요. 인접행렬말고 벡터나 리스트로 짜도 최대 V번 돌게 되어있고 최악의 경우 V번 돌 때마다 우선순위 큐에 넣는다고 가정하면

    가 틀렸습니다. 각 vertex에 대해서는 최대 V번 돌게 되어 있지만, 각 vertex 별로 도는 횟수를 합하면 E를 넘지 않습니다. \sum_v degree(v) 를 생각해보세요~


    7년 전 link
  • lsh9034
    lsh9034

    아.... 그렇군요 위에 썼던 E*V에서 탐색할 정점을 큐에서 팝할 때 팝된 경로가 전 상황에서 구한 최소경로길이보다 작으면 continue를 해도 어쨌든 가장 바깥while(!q.empty())가 E번 도는 건 맞지만 탐색을 함에 있어서는 각 정점은 한번 씩만 인접한 곳을 탐색하게 되고 그럼 V*V이지만 여기서 결국 뒤에 있는 V는 반복할수록 숫자가 작아지게 되있고 결국은 V*V(작아지는 V)라고 한다면 정확이 E번 임으로 ElogV가 되는건가요?


    7년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.