Как сложность алгоритма алгоритма Прима является ElogV с использованием Priority Q?

Question

Псевдо код, который я использовал:

for all V vertices: visited[n]=0 

pick any vertex r from graph and set visited[r]=1 

For all edges e incident to r 
PQ.insert() 

while(PQ is not empty)//line 1 
    f=PQ.min()//f(r,s) is such that visited[s]=0 
    for all edges e(s,t) incident to s//line 2 
    if(visited[t]==0) 
     PQ.insert(e);//line 3 
    else 
     PQ.delete(e);//line 4 
    visited[s]=1; 
end while; 

Согласно моему пониманию:

• линия 1: выполняет V-1 раз.
• Line 2: Сумма степени всех вершин раз ... ..это это 2E раз

Для каждой линии 2: линии 3 и 4 линии принимают log E время, потому что мы добавление/удаление всех края к/от PQ по одному.

Так общая time = V-1+2E.logE = E.log E

Но книга говорит, что это E.logV, могли бы вы объяснить, почему это так?

Answer 1

O (log (V)) и O (log (E)) являются одинаковыми.

• E не более V .
• журнал (V) = 2 * Журнал (V)
• который является O (журнал (V))

Answer 2

для всех ребер е (S, T), инцидентных с

Сколько ребер Узла s может иметь максимум?
V-1 не более. Таким образом, операции PQ имеют сложность времени O (logV).