자바에서 BFS와 DFS를 일반적인 알고리즘으로 구현하려고합니다. 문자열로 알고리즘 최악의 경우의 복잡도를 반환하는 메서드 getComplexity() 쓰고 있어요. DFS (및 BFS)에서 그래프의 각 노드는 한 번만 방문 할 수 있습니다. 최악의 경우, 각 노드는 한 번만 방문됩니다. 따라서 왜 O (V) 대신에 이러한 알고리즘 O (V + E)의 복잡성이 있습니까? 여기서 V는 노드 (또는 정점)의 수이고 E는 모서리의 수입니다.DFS와 BFS의 복잡성이 O (V)가 아닌 이유는 무엇입니까?
트리 탐색 (BFS 및 DFS)은 각 에지를 정확히 한 번 통과해야하며 각 노드를 정확히 한 번 방문해야하기 때문에 O (V + E)입니다. 트리 순회는 종종 우리에게 문제에 대한 견해를 제시하는 추상화입니다. 대부분의 간단한 경우 V와 E는 모두 사소한 연산이지만 V의 효율성은 E와 크게 다를 수 있습니다. 예를 들어 가장자리를 지나치는 것은 포인터를 따르는 것처럼 간단 할 수도 있고 그렇지 않을 수도 있습니다 네트워크를 통해 원격 호스트에서 데이터를 가져와야 할 수도 있습니다 (비싼 데이터베이스 쿼리 포함). 노드를 방문하는 것은 부울 값을 설정하는 것만 큼 간단하거나 노드의 데이터에서 값 비싼 계산을 수행 할 수 있습니다.
O (V + E)는 트리를 가로 지르는 전체적인 복잡성에 대해 판단 할 때 방문 노드와 통과 에지의 복잡성을 모두 고려해야 함을 상기시켜줍니다.
아래 표를 설명해 주시겠습니까? – Aurand
포인터를 따르는 쿼리와 외부 데이터베이스 쿼리를 구별하는 것이 알고리즘의 추상 오버추어와 아무런 관련이 없다고 생각합니다. 값 비싼 계산을 수행하는 것보다 불리언 값을 설정하는 것이 훨씬 적습니다. 이것들은 상수 요소들입니다. – torquestomp
@torquestomp 나는 V = E 일 경우 왜 V! = E. 일지를 보여주는 데 도움이 될 것이라고 생각했습니다. O (V + E) = O (2V)이고 큰 경우 - O O (2V)는 O (V) 어떤 트리에서도 모서리의 수는 노드 수 -1과 같기 때문에. – Aurand
일반적으로 그래프 E (즉, 가장자리의 수)은 (전체 그래프의 경우) 크기가 V^2입니다. 따라서 각 노드 (방문하지 않은 노드를 찾는 목적)를 검사해야한다는 사실을 무시할 수 없습니다. 검사가 각 노드를 방문하는 데 드는 비용보다 더 많은 비용이 걸릴 수 있습니다 (말했듯이 V^2 일 수 있습니다. 항상 V).
각 노드를 한 번 방문하고 각 가장자리를 한 번 탐색합니다. 그러므로 O (V + E). – Aurand
이것은 나에게 중복되는 것 같지 않습니다. 게시 한 질문의 OP는 왜 (v1 + e1 + v2 + e2 ...)인지 이해합니다. 하지만 여기서, OP가 왜 그런지 묻고 있습니다. – Cricketer