Complexity Analysis (1) - Computational Complexity (계산 복잡도)

서문 (Preface)

안녕하세요, 정우 입니다. 오랜만에 새로운 알고리즘 관련 포스팅으로 찾아뵙네요. 앞으로는 알고리즘 및 자료 구조에 관한 게시글을이 대부분을 이룰 예정입니다. (중간 중간 Distributed Systems 나 좀 흥미로운 아키텍쳐에 관한 분석글도 올리도록 하겠습니다.

 

개요 (Overview)

이번 시리즈의 주제는 바로 "알고리즘의 효율성 분석" 입니다. 그 중에서도 가장 기본이 되는 각종 수학적 Notation (표기법) 들을 알아보도록 하겠습니다.

우선 들어가기에 앞서, 일반적으로 "알고리즘" 이라 하면 떠올리시는건 대부분 코딩을 먼저 떠올리실거라 생각합니다. 하지만, 알고리즘의 사전적 정의를 보자면:

An algorithm is a finite sequence of well-defined instructions, typically used to solve a class of specific problems or to perform a computation.
(알고리즘은 유한한 갯수의 잘 정의된 명령어들을 순서대로 나열한 것으로, 일반적으로 특정한 종류의 문제들이나 계산을 하기위해 사용된다.)

 

그 중에서도, 보통 언급되는 알고리즘이라 하면 어느정도 실용성이 있는, 즉 효율적인 것들을 통칭합니다.

다시 말해 알고리즘은 단순히 코드가 아니라는 뜻이죠. 보통 알고리즘을 처음 배우는 초보자들이 많이 하는 실수가 말그대로 맨땅에 헤딩 방식으로 그냥 무작정 문제를 풀어보는건데요, 사실 효율적인 알고리즘을 짜기 위해서는 필히 효율적인 자료 구조 및 수학적 모델링을 통해 엄밀한 효율성 분석을 요구하므로 잘못된 방법이라고 볼 수 있습니다. 물론 그 중에서도 알고리즘은 보통 이산수학 (Discrete Mathematics) 의 이론들을 응용하는 경우가 대부분이므로 수학적 기반이 없다면 알고리즘을 제대로 이해하기는 힘들겠죠.

 

서론은 여기까지 하고, 이제 지금부터 나올 개념들은 앞으로 제가 포스팅할 알고리즘들이나 자료 구조들의 효율성을 분석하기 위한 수학적 모델링 방법이라고 생각하시면 되겠습니다.

 

알고리즘의 복잡도 (Complexity of Algorithms)

알고리즘의 효율성을 수학적으로 기술할때, 일반적으로 두 가지의 포인트에 초점을 맞춥니다. 바로 시간 복잡도 (Time Complexity) 와 공간 복잡도 (Space Complexity) 라는 개념입니다.

 

복잡도 (Complexity)

알고리즘의 복잡도란 Computational Complexity (계산 복잡도) 를 의미하는 것으로, 알고리즘을 (계산 가능한 기계를 통해) 실행하기 위해 사용되는 자원 (Resources) 을 의미합니다. 그 중에서도 보통 해당 알고리즘을 실행했을 때 얼마나 시간이 걸리느냐와 얼마 정도의 저장 공간 (메모리) 가 필요한가가 저희가 알아볼 복잡도구요.

 

시간 복잡도 (Time Complexity)

알고리즘의 시간 복잡도란, 간단히 정의하자면 자료의 갯수가 증가함에 따라 어떤 알고리즘을 동작시키는데 실행시키는 작업 (Operation) 의 시행 횟수 라고 생각할 수 있겠습니다. 여기서 말하는 operation 이란 구체적으로 하나의 논리적인 코드 단위라 생각할 수 있습니다 (일반적으로 프로시져 혹은 그 보다 작은 단위의 코드 덩어리를 의미합니다.)

 

이 때, 자료의 갯수를 \( n \), 걸리는 시간 (시행 횟수)을 \( c \) 라 두면 0 이상의 자연수 \( n \) 과 실행 횟수 \( c \) 의 관계를 함수 T 로 정의할 수 있습니다. 이 때, 자료 갯수의 집합을 \( N \) (\( n \in N \)), 그에 따른 실행 횟수의 집합을 \( C \) (\( c \in C \)) 라고 정의하면 그에 따른 함수 T는:

 

$$ \begin{align*} T: N \rightarrow C \; (N = \{n \;|\; n \geqslant 0, \; n \in \mathbb{N}\}, \; C = \{c \;|\; c \geqslant 0, \; c \in \mathbb{N}\}) \end{align*} $$

 

따라서 앞으로의 시간 복잡도 분석에서는 늘 자료 갯수 \( n \) 에 대한 함수 \( T(n) \) 로 두고 증명 또는 표현하도록 하겠습니다.

 

공간 복잡도 (Space Complexity)

공간 복잡도도 시간 복잡도랑 굉장히 유사한데, 말그대로 "공간" 이 여기서 메인이니 앞에서 실행 횟수 \( c \) 를 함숫값 (Image) 으로 정의했던 거와 다르게 해당 알고리즘을 실행하는데 할당된 메모리 공간, 좀 더 정확하게는 할당된 자료 (변수)의 갯수 \( v \) 와 \( n \) 의 관계를 마찬가지로 함수 \( S \) 정의할 수 있습니다.

 

$$ \begin{align*} S: N \rightarrow V \; (N = \{n \;|\; n \geqslant 0, \; n \in \mathbb{N}\}, \; V = \{v \;|\; v \geqslant 0, \; v \in \mathbb{N}\}) \end{align*} $$

 

요약 (Summary)

이번 장에서는 알고리즘의 정의와 알고리즘의 효율성을 분석할 때 계산 복잡도 (Computational Complexity) 라는 개념을 사용한다는 점, 그리고 구체적으로 여기에는 시간과 공간에 대해 각각 시간 복잡도 (Time Complexity) 및 공간 복잡도 (Space Complexity) 를 정의할 수 있다는 점을 다뤄봤습니다. 수학을 좋아하지 않는 분들 입장에서는 갑자기 수학적 표현이 나와 당황하셨을 수 있겠지만, 결국 수식이라는거 자체는 어떤 개념에 대해 모호성 (Ambiguity) 을 없애고 함축적으로 표현한 것이기 때문에 결국엔 글로 적어드린 설명과 같은 말을 하는 거라 생각하시면 될 것 같습니다.

 

(알고리즘 관련 시리즈는 기초적인 수학적 개념에 대해 어느정도 익숙하다는 전제하에 진행을 하기에 관련 개념들은 따로 찾아보시는걸 추천드립니다. 시간관계 상 이후 포스팅에서는 최대한 부가 설명은 자제하고 간단한 용어 정리 및 핵심 개념 설명 위주로 들어가도록 하겠습니다.)