Prim의 알고리즘 시간 복잡성

Question

나는보고 있었다 Wikipedia 항목 Prim의 알고리즘의 경우 인접 행렬과의 시간 복잡성이 O (v^2)이고 힙 및 인접력 목록과의 시간 복잡성이 O (e lg (v))이라는 것을 알았습니다. 그래프의 정점 수.

Prim의 알고리즘은 밀도가 높은 그래프에 사용되므로 e는 v^2에 접근 할 수 있지만, 힙과의 시간 복잡성은 O (v^2 lg (v))가됩니다. 분명히, 힙은 배열을 검색하는 것보다 성능을 향상시킬 것이지만 시간 복잡성은 그렇지 않다고 말합니다.

알고리즘은 실제로 개선으로 어떻게 느려지 는가?

Answer 1

힙이 배열을 검색하는 것을 절약하더라도 알고리즘의 "업데이트"부분이 속도가 느려집니다. 배열 업데이트는 O (1)이고 힙 업데이트는 O (log (n))입니다.

본질적으로, 당신은 알고리즘의 한 부분에서 속도를 다른 부분에서 속도로 거래합니다.

어쨌든, 당신은 n 시간을 검색해야합니다. 그러나 밀도가 높은 그래프에서는 많은 것을 업데이트해야하며 (~ v^2), 희소 그래프에서는 그렇지 않습니다.

내 머리 위의 또 다른 예는 배열에서 요소를 검색하는 것입니다. 한 번만 수행하는 경우 선형 검색이 가장 좋습니다. 그러나 많은 쿼리를 수행하면 정렬하고 매번 이진 검색을 사용하는 것이 좋습니다.

Answer 2

알고리즘 소개 (Carmen)에서

time = θ (v) · t (Extract-min) + θ (e) · t (감소 키)

                   T(EXTRACT-MIN)   T(DECREASE-KEY)   Total

1. array            O(V)             O(1)              O(V^2)
2. binary heap      O(lgV)           O(lgV)            O(E lgV)
3. Fibonacci heap   O(lgV)           O(1)              O(E + VlgV)

다른 데이터 구조를 사용하면 시간 복잡성이 다릅니다.

Answer 3

나는 당신이 어느 정도 잘못 읽은 것 같아요. 밀도가 높은 그래프의 경우,이 기사는 시간 복잡성 O (E + V log V)와 함께 Fibonacci 힙을 사용하는 것에 대해 이야기합니다.