점근적 성능 분석 방법

점근적 표기(Asymptotic notation)

• 알고리즘의 복잡도 함수 T(n)는 입력의 크기 n에 대한 수식으로 보통 여러개의 항을 가진 다항식 형태가 된다.
  ex)n^2 + 3n - 5
• 만약 n이 무한대에 가까워진다면 복잡도 함수는 최고차항만으로도 실행시간의 대부분이 반영될 수 있다
• 점근적 표기는 입력의 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 방법으로 복잡도 함수를 최고차항만을 꼐수없이 취해 단순화 시킴.
  ex)3n^2-100n+10000는 n^2으로, 2n!+ 100^n은 n!로 나타냄
• 효율성 분석에서 중요한 것은 n에 대해 "연산이 정확히 몇번 필요한가?"가 아니라 n이 증가함에 따라 "무엇에 비례하는 수의 연산이 필요한가?"이다
• 점근적 표기는 함수에 상한(Upper bound), 하한(Lower bound), 동일 등급(Tight bound)와 같은 개념을 적용하여 상한을 의미하는 빅오(Big O), 하한을 의미하는 빅오메가(Big Omega), 점근적으로 상한이면서 하한인 경우를 나타내는 빅세타(Big theta)로 표기함

빅오(Big O), 빅오메가(Big Omega), 빅세타(Big theta)

• 빅오(Big O) 표기법
• 알고리즘의 점근적 상한을 표시하는 방법
• 어떤 알고리즘이 아무리 불리한 입력이 들어오더라도 빅오의 값보다는 오래 걸리지 않음
  ex) 100n+5 < O(n^2)
• 어떤 알고리즘이 두 개의 연속적인 부분으로 나누어져 있고, 각 부분의 시간 복잡도가 각각O(g1(n))과 O(g2(n))이라면 전체 알고리즘의 복잡도는 O(max{g1(n),g2(n)})으로 더 복잡한 부분에 의해 결정된다는 의미
• 빅오메가(Big Omega) 표기법
• 알고리즘의 점근적 하한을 표시하는 방법
• 어떤 알고리즘이 최상의 값이 입력으로 들어오더라도 빅오메가의 값보다는 오래 걸림
• 빅세타(Big Theta) 표기법
• 알고리즘의 점근적 상한인 동시에 점근적 하한을 표시하는 방법
• 3개의 표기법 중에서 가장 정밀하지만, 통상적으로 빅오 표기법을 많이 사용함.

Big O 시간 복잡도 함수의 증가 속도

 

• O(1) 상수형
• n이 변하더라도 항상 일정한 시간에 처리됨
• O(logn) 로그형
• 알고리즘이 반복될 때마다 문제의 크기가 상수배 만큼 작아지는 매우 효율적인 방법
• ex) 이진탐색
• O(n) 선형
• n에 비례하는 시간이 걸리는 것으로 선형시간이라고 부름
• O(nlogn)선형로그형
• 많은 분할정복기반 알고리즘들에서 나타남
• ex) 병합 정렬이나 평균적인 경우의 퀵 정렬
• O(n^2) 2차형
• 이중 루프로 처리되는 알고리즘에서 나타남
• ex) nXn 행렬의 덧셈이나 뺄셈 등의 연산
• O(n^3) 3차형
• 삼중 루프로 처리되는 알고리즘에서 나타남
• ex) Floyd의 최단 경로 알고리즘
• O(2^n) 지수형
• ex) 원소의 개수가 n인 집합의 모든 부분집합을 찾는 문제
• O(n!) 팩토리얼형
• 입력이 수십 개만 되더라도 너무 오래 걸려서 계산 불가함

분석을 위한 일반적인 절차

1. 입력의 크기를 나타내는 파라미터를 결정
2. 기본 연산을 찾는다. 일반적으로 반복 루프의 가장 안쪽에 있다
3. 연산의 횟수가 입력 크기에 의해서만 결정되는지 확인한다. 만약 입력의 종류에 따라서도 다를 수 있다면 최선,최악,평균의 경우에 대해 독립적으로 복잡도를 분석해야 한다.
4. 기본 연산의 전체 실행횟수를 구하는 복잡도 함수 T(n)을 구한다.
5. 알려진 공식들을 이용해 T(n)을 풀고, 증가 속도를 계산한다.