코딩테스트 연습

Big-O 표기법

• 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표
• 상수와 같은 숫자는 1이 된다.

O(1) - 입력데이터의 증가에 상관없이 언제나 일정한 시간이 걸림.
O(n) - 입력 데이터의 크기에 비례하여 처리시간이 걸리는 알고리즘을 표현.
- 데이터와 시간이 같은 비율로 증가
O(n2) - n의 제곱. 데이터가 커지면 커질 수록 시간이 많이 증가.
O(nm) - n2와 거의 같지만 m에 따라 커지는 비율이 달라짐 O(n3) - 면적이 됨. n2보다 처리시간이 훨씬 더 급격히 증가함. O(2n) - 2의 n 제곱. 피보나치 수열. n3보다도 훨씬 급격히 증가함 O(log n) - 이진검색시 걸리는 시간. O(n)보다 속도가 빠름. - 검색해서 아닐때마다 반씩 찾아야 하는 부분이 줄어드는 특성 때문 O(sqrt(n)) - sqrt(n) -> 제곱근