Как анализировать время работы алгоритма Lazy Dijkstra - PullRequest
Новая
       65

Как анализировать время работы алгоритма Lazy Dijkstra

0 голосов
/ 28 мая 2020

Я пытаюсь вычислить время работы алгоритма Дейкстры. Все источники, которые я прочитал, говорят, что время выполнения составляет 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)
            }
      }
...