Dijkstra 알고리즘의 (Lazy) 실행 시간 분석

Question

Dijkstra 알고리즘의 실행 시간을 알아내려고 합니다.내가 읽은 모든 소스에서는 게으른 구현의 경우 실행 시간이 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

첫째, 일부 경계를 좀 더 엄격하게 만들고 일부를 교체할 수 있습니다. $E$와 함께 $V$에스.처음의 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()
    }
}

외부 루프가 명확하게 실행됩니다. $O(N)$ 시간, 내부 루프도 실행됩니다. $O(N)$ 여러 번(최악의 경우에는 그렇습니다).전체적으로 복잡성이 다음과 같다고 말할 수 있습니다. $O(N^2)$ 타임스.그러나 이는 단지 상한일 뿐이다.

대부분의 경우 내부 함수는 실제로 거의 작업을 수행하지 않습니다.실제로 함수를 실행한 횟수를 세어보면 constant_work(), 당신은 얻을 것이다$$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$ $N$ 반복 i == 1 그리고 그렇지 않은 경우에만 $1$ 반복.그래서 코드가 실행됩니다 $O(N)$ 시간.

노드 옆의 가장자리를 반복할 때에도 동일한 효과가 발생합니다. for (Edge edge : graph.adj(min)).네, 최악의 경우에는 $O(|V|)$ 가장자리가 희박하지만 희소 그래프에서는 대부분의 경우 훨씬 적습니다.

다른 각도에서 셀 수 있습니다.가장자리를 고정하는 경우 $(유, v)$, 얼마나 자주 그 가장자리를 만지고 루프의 몸체로 이동할 것입니까?딱 두 번!언제 한번 min == u, 그리고 한 번은 min == v.따라서 루프의 내부 부분은 런타임과 함께 $O(\로그 |V|)$, 만 실행됩니다 $O(2 |E|) = O(|E|)$ 타임스.즉, 모든 것이 실행된다는 의미입니다. $O(|E| \log |V|)$.

Answer 2

귀하의 분석이 정확하지만 단단하지는 않습니다.

while 루프와 for 루프를 개별적으로 고려하는 대신에 함께 고려하는 것이 좋습니다.For 루프의 내부 본문은 각각 (정점, 쌍) 가장자리에 대해 한 번 실행됩니다. 총 $ 2 | e | $ 시간에 대해 실행됩니다.따라서 모든 완화 작업의 총 실행 시간은 $ o (| e | \ log | e | )입니다.

모든 폴링 작업의 총 실행 시간은 $ o (| e | \ log | e | e | "$ 이며, 우리는 또한총 실행 시간은 $ o (| e | \ log | e |) $