Насколько временная сложность алгоритма Прима соответствует ElogV, использующему приоритет 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 раз.
• Строка 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².
• журнал(В²) = 2*логарифм (В)
• что является O(log(V))

Answer 2

для всех ребер e(s,t), инцидентных s

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