Сложность - алгоритм Дейкстры - PullRequest
Новая
       11

Сложность - алгоритм Дейкстры

0 голосов
/ 18 декабря 2018

Допустим, я реализовал dijkstras, используя PriorityQueue, так что добавление и удаление из невидимых узлов занимает O (log n).

PQ будет содержать не более E узлов, поэтому для его очистки мы получим O (E).Пока PQ не пуст, мы берем лучший узел и удаляем его, посещаем, если не посещали, и просматриваем всех его соседей (потенциально добавляя их в PQ).

Что я не понимаю: Каким образом обход всех соседей (в худшем случае V) для худших элементов E не имеет временной сложности O (E * V).Я видел так много объяснений, что мы должны просто смотреть на операции и наблюдать, сколько раз они будут выполняться, и делать из этого наши выводы.Я не понимаю, как мы можем игнорировать тот факт, что мы перебираем V соседей, пустой цикл for из n элементов по-прежнему равен O (n)?

Для меня окончательная сложность кажется O (V).+ E * V log E) вместо O (V + V log E).Я имею в виду, что есть много различий, но главное, я упускаю что-то тривиальное: P

1 Ответ

0 голосов
/ 18 декабря 2018

Первый пункт терминологии, который вы, кажется, запутали.E - это не количество элементов, это количество ребер между вершинами.V - это число вершин, которое (в зависимости от контекста) может быть количеством элементов.

Далее, «эта вершина является соседом этой вершины» означает, что между ними есть ребро,Каждое ребро вносит 2 соседних отношения.(По одному в каждом направлении.) Следовательно, 2 E - это количество соседних отношений, которые могут существовать, всего.

Ваша интуиция, что каждый из V узлов может иметь до V-1 соседей в общей сложности.из V<sup>2</sup>-V отношений с соседями верны, но вы можете определить, насколько вы близки к этому наихудшему случаю по числу ребер.

Поэтому мы получим следующую потенциальную работу: 

for each of E edges:
    for each vertex on that edge:
        O(1) work to check whether it was processed yet
        (processing the vertex if needed accounted for separately)

for each of V vertices:
    O(log(V)) to add to the priority queue
    O(log(V)) to remove from the priority queue
    (processing its edges accounted for separately

Первый блок - O(E).Второй кусок - O(V log(V)).Итого: O(E + V log(V)).

Надеюсь, это объяснение проясняет, почему сложность такая, какая она есть.

...