Сложность алгоритма Дейкстры для реализации кучи

Question

В книге CRLS анализ алгоритма Дейкстры выглядит следующим образом:

Сколько раз вам нужно использовать кучу?Один раз для извлечения каждого узла из кучи (т. Е. Extract-Min в книге CRLS) --- O (N);а также каждый раз, когда вы смотрите на край ---- O (E), вам может понадобиться изменить расстояние (т. е. Decrease-Key в книге CRLS), что означает исправление порядка кучи.И каждая операция кучи требует O (logN) работы.

Таким образом, общая сложность времени: O ((N + E) logN), которая равна O (ElogN), если все вершины достижимы из источника.

Мой вопрос: почему сложность становится O (ElogN), если все вершины достижимы из источника?Почему мы можем игнорировать часть O (NlogN) из O ((N + E) logN)?

Answer 1

Если все узлы соединены, должно быть как минимум N-1 ребер.Таким образом, E> = N-1 и, следовательно, N <= E + 1 и N + E <= 2E + 1, который находится в O (E). </p>

Answer 2

Если все вершины достижимы из источника, то в графе есть по крайней мере N-1 ребер, поэтому E >= N-1, N = O(E) и O((N + E) log N) = O((E + E) log N) = O(E log N)