[C로 배우는 자료 구조] 시간복잡도와 점근적 분석(2)

이번 시간에는 이진검색과 정렬에 대해 배웠다.

 

이진검색의 기본 조건

-> 배열에 저장 되어있어야 하고,

정렬되어 있어야 한다.

 

이진검색이란

우리가 영어 단어를 영어 사전에서 찾을 때와 비슷한 방법

 

배열리 있으면 그 배열의

가운데 값을 보고

내가 찾는 값이 가운데 값의

앞에 있을지 뒤에 있을지

범위를 좁혀나가면서 찾는 방법.

 

그렇게 범위를 좁혀 나가다보면

 

이렇게 first = middle = last 인 값을 찾을 수 있게 된다.

-> 내가 찾는 값!!!

 

이진검색은 한 번 실행 할 때마다

남아있는 데이터가 절반으로 줄어들기 때문에

시간복잡도는 O(log2n)

((티스토리는 수식 못넣나?;;;ㅠㅠ))

 

연결리스트에서 불가능 한 이유는

가운데 값에 먼저 접근 할 수 없기 때문

접근하려면 처음부터 접근해야하니까

 

만약 1000개의 값이 저장되어 있는 배열이라면

순차검색의 경우 1~1000번 검색해야 하지만

이진검색은 log1000번 검색해야한다.

이는 약 10번이기 때문에

순차검색과 이진검색의 차이는 매우 큰 것!

(둘의 평균 값 500번

But,

이진 검색은 10번 정도에 가능 ㅇㅇ)

 

이해가 잘 안돼 어려웠던 부분인데

완전 이해했다!

잼써