Extra
[Extra] 순차탐색 이진탐색
호호호호히히히히
2018. 3. 16. 13:42
728x90
반응형
순차탐색(Sequential search)
선형 탐색(Linear search)이라고도함
전제조건 : 없음 (정렬되지 않은 리스트여도됨)
방법 : 찾을 숫자를 처음부터 나올때 까지 비교함
ex) 1-20중 숫자 고르기 (19)
source)
int j = [찾을 숫자]
int[] arrList;
for(int i = 0; i < arrList.length; i++)
{
if (arrList[i] == j)
{
return i;
}
}
빅오 표기법 : O(N)
이진탐색 (Binary search)
전제조건 : 정렬된 데이터
방법 : 정렬된 데이터 집합을 이분화하면서 탐색하는 방법 (관계 없는 1/2을 제외시킴)
ex) 1-20중 숫자 고르기 (19)
빅오 표기법 : O(log N)
* 반씩 잘라서 찾아나가는것 "이진탐색"
* 용량이 많아질 경우 눈에 띄게 연산 횟수 차이가 나게됨
반응형