DFS와 BFS O (V + E)의 시간이 복잡한 이유

DFS와 BFS O (V + E)의 시간이 복잡한 이유

---

BFS의 기본 알고리즘 :

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

따라서 시간 복잡성은 다음과 같습니다.

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

어디 v정점은 1에n

먼저, 내가 말한 것이 맞습니까? 둘째, O(N + E)이것이 정말 좋은 이유는 무엇이며 직관은 어떻습니까? 감사

---

당신의 합계

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

로 다시 쓸 수 있습니다

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

첫 번째 그룹은 O(N)다른 그룹은 입니다 O(E).

---

DFS (분석) :

• 정점 / 가장자리 레이블 설정 / 가져 오기에는 O(1)시간 이 걸립니다
• 각 정점은 두 번 표시됩니다
  • 미완성으로 한 번
  • 한 번 방문
• 각 모서리는 두 번 표시됩니다
  • 미완성으로 한 번
  • DISCOVERY 또는 BACK으로 한 번
• 각 꼭지점에 대해 methodEdges가 한 번 호출됩니다.
• O(n + m)그래프가 인접리스트 구조로 표시되는 경우 DFS는 제 시간에 실행됩니다.
• 기억해 Σv deg(v) = 2m

BFS (분석) :

• 정점 / 가장자리 레이블 설정 / 가져 오기에는 O (1) 시간이 걸림
• 각 정점은 두 번 표시됩니다
  • 미완성으로 한 번
  • 한 번 방문
• 각 모서리는 두 번 표시됩니다
  • 미완성으로 한 번
  • DISCOVERY 또는 CROSS로 한 번
• 각 정점은 시퀀스에 한 번 삽입됩니다 Li
• 각 꼭지점에 대해 methodEdges가 한 번 호출됩니다.
• O(n + m)그래프가 인접리스트 구조로 표시되는 경우 BFS는 제 시간에 실행됩니다.
• 기억해 Σv deg(v) = 2m

---

형식이 많지 않고 매우 단순화되었습니다. 모든 모서리는 정확히 두 번 간주되고 모든 노드는 정확히 한 번 처리되므로 복잡도는 정점 수뿐만 아니라 모서리 수의 일정한 배수 여야합니다.

---

시간 복잡도는 시간 복잡도가 n ^ 2 + 2n + 7이면 O (n ^ 2)로 작성되기 때문에 O(E+V)대신에 O(2E+V)복잡합니다.

따라서 O (2E + V)는 O (E + V)로 작성됩니다

n ^ 2와 n의 차이는 중요하지만 n과 2n 사이는 중요하지 않기 때문입니다.

---

I think every edge has been considered twice and every node has been visited once, so the total time complexity should be O(2E+V).

---

Short but simple explanation:

I the worst case you would need to visit all the vertex and edge hence the time complexity in the worst case is O(V+E)

---

An intuitive explanation to this is by simply analysing a single loop:

1. visit a vertex -> O(1)
2. a for loop on all the incident edges -> O(e) where e is a number of edges incident on a given vertex v.

So the total time for a single loop is O(1)+O(e). Now sum it for each vertex as each vertex is visited once. This gives

Sigma_i

p {
    height: 50px;
    line-height: 50px;
}

span {
    position: relative;
    font-size: 2.5em;
    display: inline-block;
    line-height: .7em;
    vertical-align: middle;
}

span:before {
    font-size: 12px;
    display: block;
    position absolute;
    left: 0;
    top: 0;
    content: "V";
    width: 22px;
    text-align: center;
}

span:after {
    font-size: 12px;
    display: block;
    position absolute;
    left: 0;
    bottom: 0;
    content: "k = 1";
    width: 27px;
    text-align: center;
}

<p>
    <span>&Sigma;</span>
    O(1) + O(e)
=> 
    <span>&Sigma;</span>
    O(1)
    +
   <span>&Sigma;</span>
    O(e)

=> O(V) + O(E)

</p>

[ O(1) + O(e)]

참고URL : https://stackoverflow.com/questions/11468621/why-is-the-time-complexity-of-both-dfs-and-bfs-o-v-e