시간복잡도 O(logN) 빅오표기법

알고리즘의 효율성을 표기해주는 표기법으로

데이터가 n개 주어졌을 때 연산의 횟수를 나타낸다

빅오 표기법은 알고리즘 최악의 경우 복잡도를 나타낸다

 

 

간단하게 이진탐색을 예로 들어보자. 

 

주어진 데이터가 8개일 때 이진탐색은 8->4->2->1 이렇게 3번의 탐색을 진행해 최종적인 답을 찾아내게 된다

만약 주어진 데이터가 n개이고 x번의 탐색을 통해 1이 될 때 x는 어떻게 구할 수 있을까?

로 나타낼 수 있고 여기서 양변에 x를 구하기 위해 log(2)를 취하면

여기서 x를 구하기 위해 양변에 log2를 하면

탐색횟수 x를 구할 수 있다

 

 

O( 1) < O( log n) < O( n) < O( n* log n ) < O( n²) < O( n³)  < O( 2n ) < O( n! )

 

 

• O( 1)  : 연산횟수 고정
• O( log n)  :  문제를 해결하는 데 필요한 단계들이 연산마다 줄어듦
• O( n)  : 데이터 수와 연산횟수가 비례
• O( n* log n )  : 데이터의 수가 2배로 늘 때, 연산횟수는 2배 조금 넘게 증가

 

*log(2)n는 1/2 연산을 몇번 해야 되는지 알려주는 값이라고 생각하면 편하다

 

참고 

brenden.tistory.com/2brenden.tistory.com/2?category=747314