[알고리즘]02.점근 표기법 및 빅오 표기법

점근 표기법 (asymptotic notation)

점점 점, 가까울 근 : 점점 가까워짐

• 정수론과 해석학의 방법
• 어떤 함수가 증가하는 모습을 또 다른 함수와 비교
• 알고리즘의 복잡도를 논하거나 단순화 시킬 때 사용

컴퓨터 공학에서의 빅오 표기법

• 대문자 O를 이용해 표기
• 주로 알고리즘을 분류하기 위해 사용

O의 의미는 order of the function ( 대략 그 함수 정도)

분류하는 기준

입력 데이터가 많아짐에 따라 다음 둘이 얼마나 늘어나는지 측정

• 실행 시간 ( 시간 복잡도)
  • 알고리즘에서 주로 신경쓰는 부분
• 필요한 공간 ( 공간 복잡도)

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)

'대략 그 정도'의 의미

• 알고리즘의 실행 시간을 일반화하여 표현해서 쉽게 분류
  • 실행 시간의 예 : T(n) = 5n^2 - 5n + 3 <- 다항식의 결과가 나온다
  • 그중 최대 차항만 가지고 이야기 한다. 즉, 상기 실행 시간은 O(n^2)이 된다.

최선 vs 평균 vs 최악

• 데이터에 따라 실제 알고리즘의 실행 속도가 달라질 수 있음
• 하기 이미지는 교육 차원의 O 표기법의 성능

실무 차원에서 N^2 까지는 OK 
N^3 부터는 고민해봐야할 문제