반응형 시간복잡도2 알고리즘 BFS 와 DFS 알고리즘 공부 해봤다면 그래프에서 모든 노드를 탐색하기 위한 기법으로 BFS와 DFS 를 들어봤을 것이다. 둘의 공통 목적으로는 다음과 같다. 그래프의 탐색의 목적은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이다. 그래프의 데이터는 배열처럼 정렬이 되어 있지 않다. 그래프에서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다. 탐색 방법은 아래 그림과 같다. 모든 노드를 들려야해서 효율이 떨어질순 있지만 이부분은 백트래킹으로 해결이 가능하고 백트래킹에 대한 내용은 다음포스팅에 이어서 다뤄볼 예정이다. 특징 BFS 에 대한 특징 BFS 는 재귀적으로 동작하지 않는다. 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반.. 2022. 8. 4. 시간복잡도 계산 시간복잡도 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다. - 위키피디아- 시간복잡도를 구하는 방법은 아래와 같이 크게 3가지이다. O(Big-O) Ω(Omega) Θ(Theta) 가장 많이 쓰이는 시간복잡도는 빅오(Big-O) 표기법이므로 해당 표기법에 대한 설명을 다뤄볼 것이다. 코드를 예시로 하여 좀 더 알아보면 아래 두개의 코드를 한번 자세히 읽어보도록 한다. int sum = 0; for (int i=0; i 2022. 8. 1. 이전 1 다음 반응형
