Big O

알고리즘을 배우면서 시간복잡도에 쓰이는 Big  O 가 정확히 어떤 뜻인지 몰랐는데,

이번에 확실히 알아둬야 할 것 같아서 구글링했다.

 

알고리즘이 빠른지 느린지는 알고리즘의 단계로 판단한다.

단계가 적을수록 빠르고, 단계가 많을수록 느린 알고리즘이다. 

O(n)이라는 건, 알고리즘의 단계가 n개라는 것이다.

 

Big O는 디테일한 것은 관심없기 때문에, 상수는 제외한다.

 

2진함수는 O(logn)으로 나타낸다.

2진함수는 input을 반으로 계속 나누기 때문이다.

총 합을 반으로 몇번 나눌 것인가에 따라 결정된다.