[자바 Do It! 알고리즘]Chapter03 검색 알고리즘(복잡도-선형검색, 이진검색)
<복잡도>
1. 프로그램의 실행속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라집니다.
2. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(Complexity)라고 합니다.
3. 복잡도는 아래의 두 가지 요소를 가지고 있습니다.
1) 시간 복잡도(time Complexity) : 실행에 필요한 시간을 평가한 것
2) 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한 가를 평가한 것
<선형 검색의 시간 복잡도>
|
단계 |
코드 |
실행 횟수 |
복잡도 |
|
1 |
int i = 0; |
1 |
O(1) |
|
2 |
while(i<n) |
n/2 |
O(n) |
|
3 |
a[i] == key |
n/2 |
O(n) |
|
4 |
return i; |
1 |
O(1) |
|
5 |
i++ |
n/2 |
O(n) |
|
6 |
return –1; |
1 |
O(1) |
변수 i에 0을 대입(1단계) 하는 횟수는 처음 한번 실행한 이후에는 없습니다.
이렇게 한번만 실행하는 경우 복잡도는 O(1)로 표기합니다.
물론 메서드에서 값을 반환하는 4단계와 6단계도 한 번만 실행하기 때문에 O(1)로 표기합니다.
배열의 맨 끝에 도달했는지 판단하는 2단계와 현재 검사하고 있는 요소와 찾고자 하는 값이 같은지를 판단하는 3단계의 평균 실행횟수는 n/2입니다. 이처럼 n에 비례하는 횟수만큼 실행하는 경우의 복잡도를 O(n)으로 표기합니다.
※ 복잡도를 표기할 때 사용하는 O는 Order에서 따온 것입니다. O(n)은 'O -n', 'Order n', 'n 의 Order'라고 읽습니다.
※ 컴퓨터에게 n/2 와 n의 차이는 크지 않습니다. n의 값이 무한히 커진다고 가정하면 값의 차이가 무의미해지기 때문입니다.
1. 즉 , 2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시합니다.
2. 그러므로 선형 검색 알고리즘의 복잡도를 구하면 아래처럼 O(n)이 됩니다.
O(1) + O(n) + O(n) + O(1) + O(n) + O(1) = O(max(1, n, n, 1, n, 1) ) =O(n)
<이진 검색의 시간 복잡도>
1. 이진검색법을 이용하면 검색할 요소의 범위를 절반씩 좁힐 수 있습니다.
|
단계 |
코드 |
실행 횟수 |
복잡도 |
|
1 |
int pl = 0 |
1 |
O(1) |
|
2 |
int pr = n - 1 |
1 |
O(1) |
|
3 |
int pc = (pl + pr) /2 |
log n |
O(log n) |
|
4 |
a[pc] == key |
log n |
O(log n) |
|
5 |
return pc |
1 |
O(1) |
|
6 |
a[pc] < key |
log n |
O(log n) |
|
7 |
pl = pc + 1; |
log n |
O(log n) |
|
8 |
pr = pc - 1 |
log n |
O(log n) |
|
9 |
pl <= pr |
log n |
O(log n) |
|
10 |
return -1 |
1 |
O(1) |
이진 검색 알고리즘의 복잡도는 O(log n)입니다.(선형검색 복잡도 1번설명 참고)
