[WEEK01] 복잡도 & 점근법

복잡도 (complexity)

점근적 표기

• 알고리즘의 수행시간을 표기하기 위해, 필수적인 부분에 집중하고 불필요한 상세들은 무시

점근적 표기법 종류

• O-표기
  : 상한 표기법
  : 점근적 상한만 알고 있을 때 사용하는 표기법 ⇒ 최악의 경우에도 이 기준을 넘지 않음
  : 임의의 n값에 대해 크기 n인 특정 입력이 선택되더라도 수행시간이 O(n^2)임을 뜻함
  : 최악의 경우 수행시간이 O(n^2)이라는 뜻
  : n의 오더 또는 오더 n
  : O는 order의 머리글자 (initial)
   
• 세타표기
  : 점근적으로 어떤 함수의 위와 아래를 한계지음
  
  
• 오메가 표기
  : 점근적 하한만 알고 있을 때 사용하는 표기법 ⇒ 아무리 빨라도 이 기준보다 빠를 수 없음

 

시간복잡도(time complexity)

: 실행하는데 필요한 시간 평가

 

공간복잡도(space complexity)

: 메모리(기억공간)과 파일공간이 얼마나 필요한지 평가

 

 

점근법 (asymptotic)

: n이 커질 때 함수 f의 속성에 관심

예를 들어, f(n) = n**2 + 3n 이면 n이 커질수록 3n은 n**2에 비해 무의미해짐

 

쎄타, 빅오, 오메가

 

[참고]

[Introduction to Algorithms - Third Edition] p.43~

https://chayan-memorias.tistory.com/100