알고리즘
주어진 값 또는 값 집합을 입력(input)으로 받아 다른 값 또는 값의 집합을 출력(output)으로 생성하는 잘 정의된 계산 절차이다. 즉 알고리즘을 구성하기 위해서는 입력(input)과 출력(output)이 명확하게 정의되어야 한다. 알고리즘을 통해 입력부터 출력까지의 과정을 설명할 수 있다. 일종의 문제 해결 지침으로 생각할 수도 있다.
바람직한 알고리즘은 명확해야 하고, 이해하기 쉬워야 하며, 간결해야 한다. 과도한 기호 표기는 명확성을 저해할 수 있기 때문에 지양된다. 다양한 표현 방법이 있지만, 명확성을 해치지 않는 한 자연어를 사용하는 것도 가능하다. 가장 중요한 것은 알고리즘은 효율적이어야 한다는 것이다. 동일한 문제를 해결하는 알고리즘이라도 실행 시간 차이가 수백만배까지 날 수 있다.
알고리즘은 자연어(natural language), 흐름도(flow chart), 의사코드(pseudo code), 프로그래밍 언어(programming language) 등으로 표현할 수 있다. 자연어로 표현하면 쉽게 읽을 수 있다는 장점이 있지만, 모호할 수 있다는 단점이 있다. 흐름도는 알고리즘이 간단할 때는 이해하기 쉽다는 장점이 있지만 알고리즘이 조금만 복잡해져도 흐름도로 그리기 어렵다는 단점이 있다. 프로그래밍 언어로 표현하면 정확하다는 장점이 있다. 그러나 각 언어마다의 차이, 언어에서의 제약 등 조건이 너무 많고, 디테일해진다는 단점이 있다. 때문에 일반적으로 의사코드를 이용해 알고리즘을 표현한다.
이러한 알고리즘을 평가하는 기준은 정확성(accuracy)과 효율성(efficiency)이다. 당연하게도 알고리즘은 원하는 출력을 만들어야 한다. 알고리즘이 모든 입력에 대해 올바른 출력을 반환하면 올바르다(correct)고 한다. 잘못된(incorrect) 알고리즘은 아예 종료되지 않거나 원하는 값이 아닌 다른 값을 반환할 수 있다. 효율성은 시간적 효율성과 공간적 효율성을 둘 다 고려해야 한다. 시간적 효율서은 알고리즘의 계산 횟수에 대한 부분이고, 공간적 효율적은 알고리즘이 사용하는 메모리에 대한 부분이다.
시간복잡도 (Time Complexity)
알고리즘의 시간 효율성 측면을 시간복잡도라 한다. 또한 시간복잡도를 나타내기 위해 빅오 표기법, 빅오메가 표기법, 빅세타 표기법, 스몰오 표기법, 스몰오메가 표기법 등을 활용한다. 공간 효율성 측면인 공간복잡도 역시 빅오 표기법 등을 활용한다.
• 빅오 표기법 (Big-O notation) : $ \mathcal{O}(g(n)) $
엄격(tight)하거나 느슨한(loose) 상한(upper bound)를 표기한다.
$$ \mathcal{O}(g(n)) = \{ f(n) \mid \exists c > 0, n_0 \geq 0, \text{ s.t. } \forall n \geq n_0, f(n) \leq c g(n) \} $$
• 빅오메가 표기법 (Big-Ω notation) : $ \mathcal{\Omega}(g(n)) $
엄격(tight)하거나 느슨한(loose) 하한(lower bound)를 표기한다.
$$ \mathcal{\Omega}(g(n)) = \{ f(n) \mid \exists c > 0, n_0 \geq 0, \text{ s.t. } \forall n \geq n_0, f(n) \geq c g(n) \} $$
• 빅세타 표기법 (Big-Θ notation) : $ \mathcal{\Theta}(g(n)) $
엄격(tight)한 경계(bound)를 표기한다.
$$ \mathcal{\Theta}(g(n)) = \{ f(n) \mid \exists c_1, c_2 > 0, n_0 \geq 0, \text{ s.t. } \forall n \geq n_0, c_1 g(n) \leq f(n) \leq c_2 g(n) \} $$
• 스몰오 표기법 (Big-o notation) : $ \mathcal{o}(g(n)) $
느슨한(loose) 상한(upper bound)를 표기한다.
$$ \mathcal{o}(g(n)) = \{ f(n) \mid \exists c > 0, n_0 \geq 0, \text{ s.t. } \forall n \geq n_0, f(n) < c g(n) \} $$
• 스몰오메가 표기법 (Big-ω notation) : $ \mathcal{\omega}(g(n)) $
느슨한(loose) 하한(lower bound)를 표기한다.
$$ \mathcal{\omega}(g(n)) = \{ f(n) \mid \exists c > 0, n_0 \geq 0, \text{ s.t. } \forall n \geq n_0, f(n) > c g(n) \} $$
이러한 시간복잡도는 최고(best)의 경우, 최악(worst)의 경우, 평균적(average)인 경우로 나눠 평가하는데 최고의 경우는 큰 의미가 없어 최악의 경우나 평균적인 경우만 나타내는 것이 일반적이다. 단 평균적인 경우는 평가하기 어려운 경우가 많아 최악의 경우만 평가하기도 한다.
자료구조 및 정렬
• 자료구조 연산에 대한 시간복잡도
• 배열 정렬에 대한 알고리즘별 시간복잡도
