[하루 한문제]20180508 정렬된(sorted) n개 원소를 이진 검색 알고리즘으로 찾는다고 할 때, 최악의 상황에 놓인다면 어느 정도의 시간이 걸리나요?

[하루 한문제]

이진 검색 알고리즘

(Binary Search Algorithm)

[문제]

정렬된(sorted) n개 원소를 이진 검색 알고

리즘으로 찾는다고 할 때, 최악의 상황에 놓인

다면 어느 정도의 시간이 걸리나요?

1.Θ(log⁡n  )             2. Θ(n)              3. Θ(n^2 )            4. Θ(1)

[정답]

1번

이 문제를 맞추신 분들이 있으신가요?

사실 저도 검색을 해봐야 알 수 있었답니다.

[문제풀이]

해당 문제를 푸시려면 두가지 개념을 아셔야 합니다.

하나는 "이진 검색 알고리즘이 무엇인가?" 이고

또다른 하나는 "점근표기법이 무엇인가" 입니다.

[이진 검색 알고리즘]

먼저 이진 검색 알고리즘에 대해서 알아봅시다.

이진 검색 알고리즘은 간단히 생각하면 up-down 게임입니다.

중앙의 숫자를 선택하면 up 혹은 down으로

원하는 값을 찾아가죠

(정렬되었다는 사실을 명심하세요!)

정렬된 원소집합에 사용할 수 있다는 단점이 있지만

한번 확인마다 목표값을 찾을 확률이

두배가 된다는 장점이 있습니다.

[점근표기법]

빅오는 점근표기법 (Asymptotic Notation) 중 하나입니다.

점근표기법 종류 

대문자 O 표기법

소문자 o 표기법

대문자 오메가(Ω) 표기법

소문자 오메가(ω) 표기법

대문자 세타(Θ) 표기법

Asymptotic Growth는 함수가 증가하는 정도를 나타냅니다.

이런 증가의 기준되는 함수 f(n)이 있다고 합시다.

그리고 우리가 관심있는 함수 g(n)이 있다고 합시다.

두개 함수의 관계는 아래와 같을 것입니다.

f(n)의 증가률이 g(n)의 증가률보다 같거나

f(n)의 증가률이 g(n)의 증가률보다 느리거나

f(n)의 증가률이 g(n)의 증가률보다 빠르거나

중 하나일 것입니다.

f(n)의 증가률이 g(n)의 증가률보다 같으면

f(n) = Θg(n)이라 표기하고

f(n)의 증가률이 g(n)의 증가률보다 느리면

f(n) = o(g(n))이라 표기하고

f(n)의 증가률이 g(n)의 증가률보다 빠르면

f(n) = w(g(n))으로 표기합니다.

f(n)의 증가률이 g(n)의 증가률보다 같거나 느리면

f(n)=0(g(n))으로 표시합니다.

[생각하기]

if f(n) = o(g(n)) then g(n) = w(f(n))

[산동일크무크]

여러분 이해 안되시면, 댓글을 남겨주세요!

일크무크는 전세계의 다양한 대학교에서

공부하는 대학원생들입니다.

여러분들의 댓글이 저희를 공부하게 만들고,

더 좋은 자료를 만들 수 있도록 도와줍니다.

"배워서 남주자"라는 가치를 우리 다 함께 실천해 보아요!