Анализ времени работы алгоритма Дейкстры (ленивый)

Question

Я пытаюсь выяснить время работы алгоритма Дейкстры.Во всех источниках, которые я читал, говорится, что время работы составляет O(E * log (E)) для ленивой реализации.

Но когда мы делаем математические вычисления, мы получаем O(E * (Log(E)+E*Log(E))).

Поскольку E не является константой, я не понимаю, как можно уменьшить это значение до O(E * log (E).

Мы неправильно анализируем или можно уменьшить?

        while (!minPQ.isEmpty()) { <=== O(E)
            Node min = minPQ.poll(); <=== O(log(e)

            for (Edge edge : graph.adj(min)) { <=== O(E)
                if (min.getId() == target.getId()) {
                    // Source and Target = Same edge
                    if (edgeTo.size() == 0) edgeTo.put(target, edge);

                    return;
                }

                relax(edge, min, vehicle); <=== log(e) (because of add method on PQ)
            }
      }

Answer 1

Во-первых, вы можете сделать некоторые границы немного ужесточенными и заменить некоторые $Е$с $В$с.Цикл while в начале будет работать только $O(|V|)$ итерации (вы посещаете каждый узел только один раз), а for (Edge edge : graph.adj(min)) цикл будет выполняться только $O(|V|)$ итераций не более (узел может иметь не более $O(|V|)$ соседние края).То же самое и с коэффициентами журнала, хотя в этом случае это не имеет большого значения, поскольку $O(\log |V|) = O(\log |E|)$ (если граф связный).С помощью простого умножения это дает вам $O(|V| \cdot (\log |V| + |V| \cdot \log |V|)) = O(|V|^2 \cdot \log |V|)$.В плотном графе это уже искомая сложность.Поскольку плотный граф имеет $O(|V|^2) = O(|E|)$.

Однако в разреженном графе, например.когда $O(|E|) = O(|V|)$, то вы все равно можете добиться большего.

Проблема, с которой вы столкнулись, заключается в том, что умножение верхних границ может привести к завышению оценки.Посмотрите на следующий пример:

for (i = 1 to N) {
    limit = N if i == 1 else 1
    for (j = 1 to N) {
        constant_work()
    }
}

Внешний цикл явно работает $О(N)$ раз, и внутренний цикл также выполняется $О(N)$ раз (потому что в худшем случае так и происходит).Можно сказать, что в целом сложность $O(N^2)$ раз.Но это лишь верхняя граница.

Большую часть времени внутренняя функция практически не выполняет никакой работы.На самом деле, если вы посчитаете, сколько раз вы запускаете функцию constant_work(), ты получишь$$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$ $Н$ итерации для i == 1 и только в остальном $1$ итерация.Итак, код запускается $О(N)$ время.

Тот же эффект происходит, когда вы перебираете ребра рядом с узлом: for (Edge edge : graph.adj(min)).Да, в худшем случае у вас есть $O(|V|)$ ребра, но в разреженном графе в большинстве случаев их намного меньше.

Вы можете посчитать их под другим углом.Если вы зафиксируете край $(и, v)$, как часто вы будете касаться этого края и переходить в тело цикла?Всего два раза!Однажды, когда min == u, и однажды, когда min == v.Поэтому внутренняя часть цикла со временем выполнения $O(\log |V|)$, будет работать только $O(2 |E|) = O(|E|)$ раз.Это означает, что все это работает в $O(|E| \log |V|)$.

Answer 2

Ваш анализ правильный, но не жесткий.

вместо того, чтобы рассмотреть цикл while, а для петли по отдельности, лучше их учитывать вместе.Внутреннее тело для циклов для каждой (вершины, пара) к краю для каждой (Vertex, Pair), для общего количества 2 $ | E | $ Times.Поэтому общее время эксплуатации всех операций REALL REALL является только $ O (| E | \ log | e | $ ).

Общее время работы всех операций опроса также $ O (| e | \ log | e |) $ , как вы также наблюдаете, и выводОбщее время работы составляет $ o (| e | \ log | e |) $ .