<div id="readability-page-1" class="page"><div><h2 id="순차-탐색">순차 탐색</h2>
순차 탐색은 탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법이다. 이름에서도 알 수 있다시피 처음부터 끝까지 모두 확인하여 원하는 항목을 찾아가는 방법이다. 코드는 다음과 같다.
<pre><code>int seq_search(int key, int low, int high) {
	int i;
	
	for(i = low; i &lt;= high; i++)
		if(list[i] == key)
			return i;
	return -1;
}</code></pre>
<img src="https://velog.velcdn.com/images/jwlee010523/post/b8a04f9d-228c-4c98-8da9-bd3de2a2574a/image.png">
<h2 id="개선된-순차-탐색">개선된 순차 탐색</h2>
순차 탐색에서 비교 횟수를 줄이는 방법을 생각해 보자. 위에서 작성된 코드는 리스트 전체를 탐색하기 위한 반복문에서 리스트의 끝을 테스트하는 비교 연산이 있고 반복문 안에 키 값의 비교 연산이 있다.
아래의 코드에서는 리스트의 끝을 테스트하는 비교 연산을 줄이기 위해 리스트의 끝을 찾고자 하는 키 값을 저장하고 반복문의 탈출 조건을 키 값을 찾을 때까지로 설정하였다. 이와 같은 방법으로 탐색하면 루프 종료 조건이 단순해지고 반복 과정에서 검사할 조건이 하나로 줄어들어 성능이 개선된다. 이러한 기법을 Sentinel 기법이라고 한다.
<pre><code>int seq_search2(int key, int low, int high) {
	int i;
	
	list[high + 1] = key;
	// 키값을 찾으면 종료
	for(i = low; list[i] != key; i++);
	
	if(i == (high + 1))
		return -1; // 탐색 실패
	else
		return i; // 탐색 성공
}</code></pre>
<img src="https://velog.velcdn.com/images/jwlee010523/post/c5766ef0-1a54-424c-96b2-43dcee36d418/image.png">
<h2 id="순차-탐색의-시간-복잡도">순차 탐색의 시간 복잡도</h2>
<ul>
<li>최선의 경우: 탐색 대상이 배열의 첫 번째 원소에 위치하는 경우에는 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>이다.</li>
<li>최악의 경우: 탐색 대상이 배열의 마지막 원소에 위치하거나 없는 경우에는 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math>이다.</li>
<li>평균적인 경우에도 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math>이다.</li>
</ul>
<blockquote>
출처 
C언어로 쉽게 풀어쓴 자료구조 - 천인구
</blockquote></div></div>

jwlee010523.log

순차 탐색
순차 탐색은 탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법이다. 이름에서도 알 수 있다시피 처음부터 끝까지 모두 확인하여 원하는 항목을 찾아가는 방법이다. 코드는 다음과 같다.
int seq_search(int key, int low, int high) {
 int i;
 for(i = low; i <= high; i++)
 if(list[i] == key)
 return i;
 return -1;
}
개선된 순차 탐색
순차 탐색에서 비교 횟수를 줄이는 방법을 생각해 보자. 위에서 작성된 코드는 리스트 전체를 탐색하기 위한 반복문에서 리스트의 끝을 테스트하는 비교 연산이 있고 반복문 안에 키 값의 비교 연산이 있다.
아래의 코드에서는 리스트의 끝을 테스트하는 비교 연산을 줄이기 위해 리스트의 끝을 찾고자 하는 키 값을 저장하고 반복문의 탈출 조건을 키 값을 찾을 때까지로 설정하였다. 이와 같은 방법으로 탐색하면 루프 종료 조건이 단순해지고 반복 과정에서 검사할 조건이 하나로 줄어들어 성능이 개선된다. 이러한 기법을 Sentinel 기법이라고 한다.
int seq_search2(int key, int low, int high) {
 int i;
 list[high + 1] = key;
 // 키값을 찾으면 종료
 for(i = low; list[i] != key; i++);
 if(i == (high + 1))
 return -1; // 탐색 실패
 else
 return i; // 탐색 성공
}
순차 탐색의 시간 복잡도
최선의 경우: 탐색 대상이 배열의 첫 번째 원소에 위치하는 경우에는 $O(1)$이다.
최악의 경우: 탐색 대상이 배열의 마지막 원소에 위치하거나 없는 경우에는 $O(n)$이다.
평균적인 경우에도 $O(n)$이다.
출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구

순차 탐색(Sequential Search)

댓글