[알고리즘] 복잡도와 점근적 표기법(빅오 표기법, 빅오메가 표기법, 세타 표기법)

*한국기술대학교 원격평생교육원에서 수강중인 학점은행제 컴퓨터공학 학사 과정의 알고리즘 요약 자료(시험 대비)입니다.

 

 

<점근적 표기법>

복잡도의 점근적 표기

• 점근적 분석 : 입력의 크기가 충분히 큰 경우에 대한 분석
• 입력 크기가 작은 문제 : 알고리즘의 효율성이 중요하지 않음(비효율적인 알고리즘도 큰 문제가 없음)
• 입력 크기가 충분히 큰 문제 : 알고리즘의 효율성이 중요(비효율적인 알고리즘이 치명적)
• 복잡도는 입력 크기에 대한 함수로 표기하며, 이 함수는 주로 여러 개의 항을 가지는 다항식
• 다항식을 단순한 함수로 표현하기 위해 점근적 표기법 도입
• n의 크기가 커짐에 따라 최고차항을 제외한 나머지 항의 비중이 줄어들기 때문에, 일반적으로 최고차항만을 표기

 

O(Big-Oh) 표기법

• 점근적 상한선, 최악의 경우의 알고리즘 수행 시간을 나타냄
• 최악의 경우에도 성능을 보장하기 때문에 가장 많이 사용하는 알고리즘 성능 표기 방식
• 실제 시간 복잡도(f(n))가 특정 n값 이상에서 항상 추정 시간 복잡도(c*g(n))보다 작음을 증명하여, 최고차항의 계수와, 최고차항 이외의 모든 항을 제거하고 단순한 형태인 O(n)과 같이 표기할 수 있는 근거를 만듦
• 적어도 O(g(n))보다 나빠지지 않음

 

Ω(Big-Omega) 표기법

• 점근적 하한선, 최선의 경우 알고리즘 수행 시간을 나타냄(위험성이 큰 가정이므로 거의 사용되지 않음)
• 실제 시간 복잡도(f(n))가 특정 n값 이상에서 항상 추정 시간 복잡도(c*g(n))보다 큼을 증명하여, 최고차항의 계수와, 최고차항 이외의 모든 항을 제거하고 단순한 형태인 Ω(n)과 같이 표기할 수 있는 근거를 만듦
• 적어도 Ω(g(n))보다 좋아지지 않음

 

Θ(Theta) 표기법

• 점근적 상한선과 점근적 하한선의 교집합
• n0보다 큰 모든 n에 대해 f(n)이 상한과 하한을 동시에 만족함을 의미