Week1-2 Asymptotic Analysis_Linear and Binary Search

Linear Search: 선형 탐색

특정 값을 찾기위해, 맨 앞에서부터 순서대로 하나하나 확인하는 탐색방법이다.

앞에서 설명했던, 임의의 정수 n개가 들어간 n개의 배열에서 최댓값을 찾는 경우 또한 선형탐색이라 볼 수 있다.

최악의 경우, n번 시행하므로, 선형탐색의 Time complexity 는 n의 꼴의 함수로 표현할 수 있다.

이떄, 앞의 계수나 뒤에 더해진 상수값은 굳이 신경쓰지 않아도 된다.

Asymptotic Analysis 는 n이 무한대로 갈때로 가정하기 때문에 n의 계수의 차이와 상수값의 차이는 고려하지 않고, 만약 T(n)의 꼴이라면 Asymptotic Analysis 관점에서 본다면 같은 Time Complexity 를 가지고 있다고 할 수 있음.  

Binary Search: 이진 탐색

미리 오름차순이나 내림차순으로 정렬되어있는 데이터를 대상으로한다.

이게 무슨말이냐 하면, 100개의 정렬된 1부터 100까지의 숫자가 써있는 카드가 존재한다고 가정하자.

여기서, 33이라는 숫자를 찾으려고한다.

그렇다면, 우선 100개의 카드뭉치를 반으로 가른다.

그렇게되면 1-50 과 51-100 의 두 카드뭉치가 있고, 첫번째 카드뭉치를 제외하고 나머지 카드뭉치는 고려대상에서 제외시키자. 너가찾으려는 값은 33이니까 보지않아도된다. 

이런식으로 크기는 한번 수행할때마다, 전체 갯수의 절반이 되고, 찾으려는 값 33이 나올때까지, 즉 카드의 갯수가 한장이 될때까지 수행하면된다. 

 

이걸 일반화해서 표현해보자.

n   ->   n * 1/2   ->   n * 1/2 * 1/2   ->   ....   --> n *(1/2)^K    ( n은 데이터의 갯수, K는 시행횟수 )

 

n *(1/2)^K = 1 을 만족해아한다. 

K에 대해 정리

--> K= log 2 n

 

따라서, 이진탐색의 그래프는 로그함수의 형태를 띄고, 선형탐색의 그래프는 직선의 형태를 띄게된다.

시행횟수가 적을수록 좋으므로, 함수값이 더 아래에 분포되어있는 Binaty Search가 시간복잡도 측면에서 Linear Search 보다 좋은 알고리즘이라고 말할 수 있다.