편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
463번째 줄: | 463번째 줄: | ||
===== 순차 탐색 ===== | ===== 순차 탐색 ===== | ||
말 그대로 시작점부터 순차적으로 탐색하는 것이다. 전부 탐색한다고 생각할 때,연산량은 O(n)이다.<br | 말 그대로 시작점부터 순차적으로 탐색하는 것이다. 전부 탐색한다고 생각할 때,연산량은 O(n)이다.<br> | ||
솔직히 이건 해당 언어만 알면 누구나 코드를 만들어낼 수 있을 수준이기에,소스 코드 부분은 생략한다. | 솔직히 이건 해당 언어만 알면 누구나 코드를 만들어낼 수 있을 수준이기에,소스 코드 부분은 생략한다. | ||
472번째 줄: | 472번째 줄: | ||
배열 1 3 4 7 8 13 17에서 '8'이 있는 위치를 찾는다고 가정하자. | 배열 1 3 4 7 8 13 17에서 '8'이 있는 위치를 찾는다고 가정하자. | ||
배열: 1 3 4 7 8 13 17<br | 배열: 1 3 4 7 8 13 17<br> | ||
1st:총 배열의 가운데인 7을 선택.<br | 1st:총 배열의 가운데인 7을 선택.<br> | ||
7<8 이므로 더 큰 숫자가 있는 오른쪽으로 진행. <br | 7<8 이므로 더 큰 숫자가 있는 오른쪽으로 진행. <br> | ||
2nd:7~17의 배열중 가운데인 13을 선택.<br | 2nd:7~17의 배열중 가운데인 13을 선택.<br> | ||
13>8 이므로 더 작은 숫자가 있는 왼쪽으로 진행.<br | 13>8 이므로 더 작은 숫자가 있는 왼쪽으로 진행.<br> | ||
3rd:7과 13의 가운데에 있는 8을 선택.<br | 3rd:7과 13의 가운데에 있는 8을 선택.<br> | ||
8=8 이고 배열은 5번째이므로 답은 5이다. | 8=8 이고 배열은 5번째이므로 답은 5이다. | ||
504번째 줄: | 504번째 줄: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
이것을 변형하면,배열의 어디부터가 어떤 숫자 이상인지 혹은 초과인지 알 수 있다.<br | 이것을 변형하면,배열의 어디부터가 어떤 숫자 이상인지 혹은 초과인지 알 수 있다.<br> | ||
전자가 Lower bound,후자가 Upper bound이다. 이들은 아예 <algorithm>에 포함된 함수가 있으니 한번 봐두자. | 전자가 Lower bound,후자가 Upper bound이다. 이들은 아예 <algorithm>에 포함된 함수가 있으니 한번 봐두자. | ||
<syntaxhighlight lang="cpp"> | <syntaxhighlight lang="cpp"> | ||
565번째 줄: | 565번째 줄: | ||
G[i].push_back (x); //i와 x는 연결된 그래프이다. | G[i].push_back (x); //i와 x는 연결된 그래프이다. | ||
</syntaxhighlight> | </syntaxhighlight> | ||
이 때,탐색시간은 인접 리스트 방식의 구현이 더 짧다.(단,v가 정점이고 e가 간선이라고 가정한다.)<br | 이 때,탐색시간은 인접 리스트 방식의 구현이 더 짧다.(단,v가 정점이고 e가 간선이라고 가정한다.)<br> | ||
인접 행렬:O(v*e)<br | 인접 행렬:O(v*e)<br> | ||
인접 리스트:O(v+e) | 인접 리스트:O(v+e) | ||