Временная сложность алгоритма простых чисел?

Question

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

Похоже, сложность по времени равна O (V (log V + E log 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.Adjacent[u]
9           if v ∈ Q and w(u, v) < v.key
10              v.π ← u
11              v.key ← w(u, v)

Использование двоичной кучи

1. Сложность времени, необходимая для одного звонка EXTRACT-MIN(Q) является O(log V) используя очередь с минимальным приоритетом. Цикл while в строке 6 выполняет всего V times.so EXTRACT-MIN(Q) называется V раз. Так сложность EXTRACT-MIN(Q) является O(V logV),

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

3. for цикл в строке 1 будет выполнен V раз. Использование процедуры для выполнения строк с 1 по 5 потребует сложности O(V),

Общая сложность времени MST-PRIM является суммой временной сложности, необходимой для выполнения шагов с 1 по 3, в общей сложности O(VlogV + (E logV + V) = O(E logV),

Использование кучи Фибоначчи

1. То же, что и выше.
2. Выполнение строки 11 требует O(1) амортизированное время Строка 11 выполняет в общей сложности 2E раз. Таким образом, общая сложность времени O(E),
3. То же, что и выше

Таким образом, общая сложность времени MST-PRIM сумма выполнения шагов с 1 по 3 для общей сложности O(V logV + E + V)=O(E + V logV),

Answer 2

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

Answer 3

Временная сложность алгоритма простых чисел O(VlogV + ElogV). Мне ясно, что вы понимаете, как появился VlogV .

Теперь, как получается ElogV, так что сначала посмотрите на prims algo

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) }

ваша проблема лежит в строке 8 до 11 . Как вы можете легко видеть, строки с 8 по 11 выполняются для каждого элемента в Q, и мы знаем, что количество элементов в Q равно V . Теперь рассмотрим это для 1-го элемента Q, мы запускаем цикл в строке 8 для каждого его соседа и делаем то же самое для его следующего элемента, и то же самое для всех остальных элементов Q . так как количество элементов в Q равно V, поэтому мы запускаем цикл в строке 8 ровно 2E раз. EX:-

   1
  / \
 2---3

теперь предположим, что элементы в Q будут в порядке 1, 2,3 . Если мы запустим цикл в строке 8 для первого элемента из Q i,e 1, мы выполним его ровно 2 раза (мы проверяем каждого из его соседей) и для 2 мы запускаем цикл в строке 8 2 раза и 3 раза. Теперь мы получаем 2+2+2 = 6(общее количество раз выполнения цикла в строке 8), что равно 2*E (где E - общее число ребер в графе), поэтому сложность времени для строки 8–11 становится

O(2*ElogV) мы отбрасываем константы в биг-о, так что сложность становится

O(ElogV) 

теперь общая временная сложность алгоритма становится O(VlogV + ElogV) = O((V+E)logV)

В плотном графе E>V, поэтому во временной сложности мы игнорируем V и получаем

O(ElogV) 

Answer 4

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