Сложность алгоритма Примса?

Question

Я нашел временную сложность алгоритма Примса во всем мире как O ((V + E) log V) = E log V. Но, как мы видим, алгоритм:

Похоже, что временная сложность является O (V (вход V + E журнала V)). Но если его временная сложность равна O ((V + E) log V). Тогда вложенности должны быть, как это:

Но выше вложенности кажется неправильным.

Answer 1

MST-PRIM(G, w, r) 
1 for each u ∈ G.V 
2  u.key ← ∞ 
3  u.π ← NIL 
4 r.key ← 0 
5 Q ← G.V 
6 while Q ≠ Ø 
7  u ← EXTRACT-MIN(Q) 
8  for each v ∈ G.Adj[u] 
9   if v ∈ Q and w(u, v) < v.key 
10    v.π ← u 
11    v.key ← w(u, v) 

USING A BINARY HEAP

1.Here вы можете увидеть, что время, необходимое для одного вызова EXTRACT-MIN(Q)=O(log V) [с использованием мин очереди приоритета] .The во время цикла в строке 6 выполняет общую V times.so приточно-MIN (Q) называется V times.so общее время, необходимое для EXTRACT-MIN(Q)=O(VlogV).

2. цикл for в строке 8 выполняется всего 2E раз (как общая длина всех списков смежности = 2E для неориентированного графика). Время, необходимое для выполнение строки 11 = O (log v) [с использованием операции DECREASE_KEY на минимальной куче). Строка 11 выполняет всего 2E раз. требуется выполнить строку 11 = O (2Elog V) = O(Elog v).

3. цикл в строке 1 будет выполняться для процедуры BUILD_HEAP V times.using, чтобы выполнить строки с 1 до 5, это потребует O(V) раз

Общее время сложность МСТ-PRIM = время, необходимое для выполнение 1 + время, необходимое для выполнения 2 + время, необходимое для выполнения 3 = O (VlogV + ElogV + V) = O (ElogV)

USING A FIBONACCI HEAP 

1. То же, что и выше.

2. Строка выполнения 11 требуется O (1) амортизированная time.line 11 выполнена всего 2E раз. Общая сложность времени = O (E).

3. То же, что и выше

Так общей временной сложности МСТ-PRIM = время, необходимое для выполнения 1 + время, необходимое для выполнения 2 + время, необходимое для выполнения 3 = O (VlogV + Е + В) = О (Е + VlogV).

Answer 2

Фактически, как вы говорите, как вложен внутри, а сложность времени должна быть v.E lg V правильной в случае асимптотического анализа. Но в cormen они сделали амортизированный анализ, поэтому он выходит (Elogv)

Answer 3

Ваша идея кажется правильной.Давайте сложность, как V(lg(v) + E(lg(v))) Тогда обратите внимание, что во внутреннем цикл, мы на самом деле происходит через все вершины, а не ребра, поэтому давайте изменим немного V(lg(v) + V(lg(v))) что означает V(lg(v)) + V*V(lg(v)) Но для анализа наиболее неблагоприятного случая (плотные графики), V * V примерно равно числу ребер, E V(lg(v)) + E(lg(v)) (V+E((lg(v)) но так как V << E, следовательно, E(lg(v))