[알고리즘] 점근적 표기법(Asymptotic Notation)

알고리즘의 성능

알고리즘을 구현하고 나서 이 알고리즘의 성능이 어떤지를 모르면 알고리즘을 더 개선할 수도 사용할 수도 없다. 그렇기 때문에 알고리즘의 성능을 측정할 수 있는 기준들이 필요한데 정렬 속도, 특정 데이터에 빠른 접근, 메모리 사용량 등 알고리즘의 성능을 가리는 기준은 여러 가지가 있을 수 있다. 그 중 아래에 5개의 기준이 대표적인 측정기준이다.

1. 정확성

   • 정확하게 동작하는가
   • 몇 번의 입력에도 언제나 정확한 출력을 하지 않는 알고리즘은 쓸모가 없음

2. 작업량

   • 얼마나 적은 연산을 수행하는가
   • 적은 연산으로 요구되는 기능을 완벽하게 수행할 수 있어야함
   • 글자를 탐색하는 알고리즘은 본문에서 특정 패턴을 비교하는 비교 횟수, 데이터를 정렬하는 알고리즘은 데이터를 비교하는 횟수가 작업량이라고 할 수 있다.

3. 메모리 사용량

   • 얼마나 적은 메모리를 사용하는가
   • 알고리즘이 작업을 수행하는 과정에서 메모리 양은 최대한 적게 사용할 수 있도록 해야함
   • 데이터를 정렬하기 위해서 추가되는 데이터의 양이 메모리 사용량이다.

4. 단순성

   • 얼마나 단순한가, 복잡한 알고리즘은 분석, 개선이 어렵다.

5. 최적성

   • 개선할 여지가 없을 만큼 최적화 되어있는가
   • 위의 4가지 조건을 얼마나 충족하는가

알고리즘의 수행 시간

알고리즘 수행 시간이란, 알고리즘이 수행되어 시작부터 종료되는 시간까지의 차이를 말하는 것이 아니다. 그 이유는 하드웨어의 성능에 따라서 같은 알고리즘이라도 수행되는 시간이 달라지기 때문이다. 하드웨어의 성능에 관계 없이 명확하게 정의하려면 입력 데이터의 크기의 변화에 대한 수행 시간의 변화를 예측할 수 있어야하는데, 이 작업에 활용될만한 후보로 작업량을 꼽을 수 있다. 알고리즘 수행 시간 분석은 최악의 경우, 평균의 경우, 최선의 경우를 찾는 것이 목표이다.

점근적 표기법이란?

알고리즘의 수행 시간을 요약해서 나타내는 표기법이다. 중요하지 않은 항과 상수 계수를 제거하면 이해를 방해하는 불필요한 부분이 없어져서 알고리즘의 실행 시간에서 중요한 부분인 성장률(입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지)에 집중할 수 있다. 상수 계수와 중요하지 않은 항목을 제거한 것을 점근적 표기법이라고 한다. 대표적으로 Big-O, Big-Ω, Big-θ 3가지가 있다.

Big-O(Big O)

최악의 경우의 성능, 즉 수행 시간의 상한을 표기한다. 시간 복잡도를 표기할 때 해당 표기법을 가장 많이 사용하는데, 어떠한 기능의 수행 시간에 대해서 대충 10분 정도 걸려라는 표현보다 10분 이상은 절대 걸리지 않아라는 표현이 기능을 더 명확하게 파악하게 해주기 때문이다.

• 최대 수행 시간이 2n² + 4n 또는 n²/2 알고리즘인 경우 O(n²)

Big-Ω(Big Omega)

최선의 경우의 성능, 즉 수행 시간의 하한을 나타냄.

• 최선의 수행 시간이 3n² + 8n인 알고리즘인 경우 Ω(n²)

Big-θ(Big Theta)

O 표기법과 Ω 표기법을 모두 만족시키는 증가 함수를 뜻함.

• θ(f(n)) = O(f(n))⋂Ω(f(n))

시간 복잡도 계산법

알고리즘의 실행 시간이 아닌 핵심이 되는 연산 횟수를 센다.

a = 0                   # 1
for i in range(n):      # n
    a += 1              # n
# 2n + 1 => O(n)

공간 복잡도 계산법

메모리를 얼마나 사용하는지 계산한다.

a = [['a']] * n  # n * n
# n * n => n²