كيف تعقيد وقت الخوارزمية في الوقت المناسب elogv باستخدام الأولوية س؟

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: مجموع درجة من جميع القمم أوقات ....that هو 2E مرات

لكل سطر 2: السطر 3 والخط 4 log E الوقت لأننا نضيف / حذف جميع الحواف إلى / من PQ واحدا تلو الآخر.

إجمالي ذلك time= V-1+2E.logE = E.log E

لكن الكتاب يقول أنه E.logV, ، هل يمكن أن تفسر لماذا هذا؟

Answer 1

o (سجل (v)) و o (سجل (e)) هو نفسه.

• ه على الأكثر الخامس².
• سجل (خامسا²) = 2 * سجل (v)
• وهو o (سجل (v))

Answer 2

لجميع الحواف E (S، T) حادث

كم عدد حواف العقدة s يمكن أن يكون على الأكثر؟
V-1 في الغالب. لذلك، تعقيد العمليات PQ O (LOGV) التعقيد.