[알고리즘] 알고리즘 분석, Big-O notation, 마스터 정리

교재 Introduction To Algorithms 3rd Edition를 바탕으로 수업시간에 다룬 내용 위주로 정리하였다.

​

알고리즘 기본 용어 정리

매개변수((parameter))는 문제에서 언급된 할당되지 않은 변수들이다.

문제 : 오름차순으로 n개의 정수 리스트 S를 정렬하시오. → 매개변수 : n, S

​

실체((instance))는 매개변수에 실제로 할당된 값이다.

→ 문제 : 오름차순으로 n개의 정수 리스트 S를 정렬하시오. → 실체 : n = 6, S = [10, 7, 11, 5, 13]

​

알고리즘이란 어떤 수학적으로 엄밀히 정의된 문제를 풀기 위한 유한한 절차와 방법이다.

---

알고리즘의 실험적 분석

주어진 알고리즘을 소스코드로 구현한 다음, 실제 환경에서 동작시켜 실제 실행 시간을 측정하여 분석한다. C언어에서는 clock()함수를 이용해서 측정 가능하다.

​

실험적 분석 방법에는 크게 두 가지 단점이 있다.

1. 알고리즘을 실제로 구현해야 한다.
2. 여러 알고리즘의 성능을 비교할 때, 하드웨어 사양 및 측정할 수 없는 다양한외부 요인들로 인해 정확한 비교가 힘들다.  

 

---

알고리즘의 이론적 분석

알고리즘을 실제 수행 시간이 아닌, high-level에서 이론적으로 기술하는 방법이다. 사용하는 하드웨어 및 소프트웨어와 무관하게 알고리즘의 성능을 표현한다. 이론적 분석을 통해 구한 알고리즘 수행 시간을 시간 복잡도라 한다. 숫자를 변수에 할당하거나 사칙 연산 등의 단일 연산들은 입력 크기와 무관하게 상수 시간(O(1)같은)이 소모된다.

---

Big-O notation과 같은 알고리즘의 시간 복잡도 표기법

실제 성능에서 복잡한 알고리즘일수록 기본 연산들의 속도차이는 거의 무의미하고 입력 사이즈에 비례해서 해당 함수가 어느 정도로 수행 시간이 증가하는가가 중요하다.

 

Big-Oh notation은 입력크기 n에 대해 최악의 경우 걸리는 시간이다.

Omega Notation은 입력크기 n에 대해 최고의 경우 걸리는 시간이다.

Theta Notation은 입력크기 n에 대해 평균적으로 걸리는 시간이다.

​

n! 은 Strling's approximation에 의해 $ O(n^n) $으로 취급한다.

​

이렇게 설명만 보면 이해하기 어려울 수 있다. 여러 알고리즘들을 직접 분석해 보고 계속 연습하는 방법이 도움이 많이 될 것이다. 예를 하나만 들자면, for문으로 n사이즈의 배열에 대해 사칙연산 같은 명령을 실행했다면 이 알고리즘은 O(n)이다.

---

마스터 정리

시간 복잡도를 구하는 방법은 여러가지 존재하지만 마스터 정리는 알아두면 좋을 것 같다. $T(n) = aT(n/b) + f(n)$과 같은 모양을 가진 점화식에 대해 시간 복잡도를 아래의 $h(n)$으로 판단할 수 있다.

 

$ h(n)=n^{(\log _ba)} $

 

마스터 정리를 풀어서 해석해보면 아래와 같다.

1. h(n)이 더 무거우면 h(n)이 수행 시간을 결정한다.
2. f(n)이 더 무거우면 f(n)이 수행 시간을 결정한다.
3. h(n)과 f(n)이 같은 무게이면, h(n)과 log n의 곱이 수행 시간이 된다.