[week02] 정렬 + 이진탐색 vs 선형탐색(순차탐색) 시간복잡도

점근 표기법(Asymptotic Notation)

점근 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 우리는 이를 알고리즘의 복잡도를 단순화할때 쓴다. 

어떻게? 가장 큰 영향을 주는 항만 계산하는 방식으로 단순화 시킨다.

 

점근적 표기법에는 대표적으로 3가지가 있다.

• 최상의 시나리오를 기준으로 하는 표기법: 오메가 표기법
• 평균적인 시나리오를 기준으로 하는 표기법: 세타 표기법
• 최악의 시나리오를 기준으로 하는 표기법: 빅오 표기법(Big-O Notaion)

우리가 주로 사용할 빅오 표기법은 실행 시간의 상한을 나타내며, 다른말로 하면 최악을 생각하는 경우이다. 컴퓨터공학자들은 일반적으로 최악을 상황을 고려하고 프로그래밍을 짜기 때문에 Big-O 표기법을 많이 쓴다.

책에서 배운 내용과 다르다??

책에서 배우기로는

정렬 알고리즘의 시간복잡도는 O(NlogN)이라고 한다.

이진탐색의 시간복잡도는 O(logN)이다.

선형탐색의 시간복잡도는 O(N)이다.

 

그런데 이진탐색은 항상 정렬을 하고 탐색을 진행해야 한다.

일반적으로 생각하면 [정렬] O(NlogN) + [이진탐색] O(logN)이고, 전체 복잡도는 차원이 가장 높은 복잡도를 따라가기 때문에 O(NlogN)이라고 생각할 수 있다.

선형탐색은 O(N)이다.

뭐야? 선형탐색이 더 빠르잖아! 그럼 이진탐색은 왜하는거야? 라고 나처럼 단순하게 생각할 수 있다.

* 복잡도 크기비교
감소 <---------------------------------------------------> 증가
         1   logn   n   nlogn   n^2    n^k   2**n    n!

그런데 [백준 1920번 수 찾기] 문제를 실제로 풀어보면 [선형탐색]으로 풀었을 때는 시간초과가 나고 [정렬 후 이진탐색]으로 풀었을 때는 통과를 하는 경험을 할 수 있다. 

 

???

 

이 문제를 해결하기 위해서 여러 블로그들을 둘러보았지만 대부분 

'내가 실행하는 프로그램이 무엇인지에 따라서 탐색방식을 선택해야 한다.'

'리스트의 정렬유무에 따라 사용자가 적합한 알고리즘을 선택해야 한다.'

'이진탐색시에는 정렬을 포함하기 때문에 선형탐색보다 무조건 좋다고 할 수 없다.'

등의 대략적인 말들만 찾을 수 있었다.

 

며칠간 의문인 상태로 묵혀두고 있었는데, 같은 조의 엄청난 형이 답을 찾아내서 알려주었다. 

(아래 블로그에 정리도 깔끔하게 되어있다.)

https://beeehappy.tistory.com/12

선형탐색과 이진탐색

내가 이해한 방식대로 간단히 설명을 해 보자면

 

N=100이라고 가정했을 때(전체 수의 개수)

 

만일 1개를 search한다고 생각해보자(K=1).

정렬 후 이진탐색 : O(NlogN) + K * O(logN) = O((N+K)logN) = O(101*2) = O(202)

선형탐색: K * O(N) = O(K*N) = O(100)

이므로 내가 앞에서 예상했던 대로 선형탐색이 더 빠르다!! 

 

그러나 K개를 search한다고 가정해보자.

정렬 후 이진탐색:  O(NlogN) + K * O(logN) = O((N+K)logN)

선형탐색: K * O(N) = O(K*N)

정렬 후 이진탐색 = O(200log100) = O(400)

선형탐색 = O(100*100) = O(10000)

 

더 나아가서

문제에서 주어진 범위인 1<=N<=100000, 1<=K<=100000 중에

최대범위인 N = 10^5, K = 10^5을 대입해보자.

정렬 후 이진탐색:  O(NlogN) + K * O(logN) = O((N+K)logN)

선형탐색: K * O(N) = O(K*N)

정렬 후 이진탐색 = O(10^6log10^6) = O(10^6*6) = O(6,000,000)

선형탐색 = O(10^6*10^6) = O(10^12)    =   O(1,000,000,000,000)

N과 K가 늘어날 수록 둘의 시간복잡도의 차이는 기하급수적으로 증가한다.

 

이처럼 찾으려는 개수 K와 탐색해야 하는 전체 수 N에 따라서 같은 식에서도 다른 시간복잡도가 나온다.

이제서야 블로그에서 봤던 '내가 실행하는 프로그램에 따라서 탐색방식을 선택해야 한다.'의 의미를 알 수 있었다. (그냥 두루뭉술한 설명이 아니라 정답이었다)

 

내가 한글로 찾았을때는 나오지 않던게 조원형이 영어로 찾으니까 나온것을 보고 영어로 검색하는 습관을 길러야겠다고 생각했다. 운영진분들 말씀(정글의 핵심은 기본 동작 원리 + 구글링 키워드만 던져주기. 팀스터디 하면 된다)중에 틀린게 하나 없다...

 

---

참고자료

https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95

https://blog.chulgil.me/algorithm/

https://ratsgo.github.io/data%20structure&algorithm/2017/09/13/asymptotic/