[알고리즘] 빅 오 표기법

알고리즘 성능 예측이 목표

 

- 상수는 과감하게 버린다

- O(1) : 입력 데이터에 상관없이 언제나 일정한 속도로 결과를 반환

            Linear 

- O(n) : 데이터가 증가함에 따라 처리시간도 증가

- O(n^2) : 2중 for문이 대표적 (면적)

- O(n^3) : 3중 for문이 대표적 (큐빅)

                 n^2 보다 데이터 증가에 따른 처리속도가 급격하게 증가

- O(2^n) : 피보나치 수열

- O(log n) : 이진 검색, O(n)에 비해 데이터 증가에 따른 처리속도의 증가가 완만하다

- O(Square(n)) : (=제곱근) 

 

참고 유투브 영상

youtube.com/watch?v=6Iq5iMCVsXA