■ 계산 복잡도 이론 (Computational Complexity Theory)
좋은 알고리즘이란 무엇인가?
- 빠르게 문제를 해결하는 알고리즘
- 메모리를 적게 쓰는 알고리즘
두 가지를 좋은 알고리즘이라고 하는 것 같다.
그래서 사람들은 어떤 알고리즘이 얼마나 좋은 성능을 가지는지 분류해 보고자 했고, 그래서 탄생한 것이 계산 복잡도 이론이다.
빠르게 해결하는 알고리즘 --> "시간 복잡도 이론 (Time Complexity)"
메모리를 적게 쓰는 알고리즘 --> "공간 복잡도 이론 (Space Complexity)"
보통 공간 복잡도 보다는 시간 복잡도를 중요하게 다룬다.
왜일까...?
- 하드웨어 공간이 작은 경우에만 공간 복잡도를 고려하기 때문이다.
(요즘은 하드웨어 및 메모리가 꽤 커지긴 했다) - 공간 낭비는 보통 구현 과정에서의 문제일 가능성이 크기 때문이다.
- 공간 복잡도는 이론적으로 시간 복잡도보다 작을 수밖에 없기 때문이다.
사실 3번은 잘 모르겠지만 이렇게 이해했다.
메모리 공간에 접근, 수정하는 과정에서는 무조건 시간이 걸린다.
"메모리를 할당받아두고 의도적으로 안 쓰는" 알고리즘 같은걸 제외한다면,
n회의 연산을 했다면 -> 매 연산마다 다 다른 메모리 공간을 썼다고 하더라도 n에 비례하는 공간을 썼을 것이다.
이 게시글에서도 시간복잡도 이론만 정리해 보려고 한다.
■ 시간 복잡도 이론 (Time Complexity)
알고리즘의 시간 효율성은 어떻게 측정 가능한가?
그냥 시간으로 측정하기에는 문제가 있다.
슈퍼 컴퓨터와 일반 컴퓨터, 10년 된 컴퓨터에서 실행하면 시간이 다 다를 것이다.
이런 형태로 비교하는 것은 의미가 없다.
--> 즉, 하드웨어의 성능이 달라져도 같은 값이 나와야 한다.
또한, 알고리즘에서 중요한 것은 입력값의 개수에 따른 수행 시간의 변화이다.
알고리즘은 자료구조에서 문제를 해결하기 위한 절차이다.
자료구조는 여러 개의 데이터를 저장하는 방식이다.
--> 즉, 데이터의 개수가 많아질 경우에도 알고리즘이 어느 정도의 시간으로 동작할 지 알 수 있어야 한다.
따라서, 알고리즘의 시간 복잡도는 연산의 단계 수(step)에 따라 표시한다.
데이터가 n개일 때 알고리즘의 수행 시간은 n에 대한 함수인 f(n)으로 표시할 수 있다.
이때 f(n)은 일반적으로는 n에 대한 다항식(Polynomial)이지만, 2^n 등 다항식이 아닌 경우도 있다.
예를 들어 어떤 알고리즘의 수행 시간이 f(n) = n^2+5*n+3 이라면
데이터가 1개 (n=1) 일 때 9번의 step,
데이터가 10개(n=10)일 때 153번의 step,
... 이 걸린다고 보는 것이다.
다만, 실제로 이렇게 긴 함수로 표시하게 되면 알고리즘의 성능을 한 눈에 알 수 없다.
알고리즘의 성능을 보다 단순하게 나타내기 위해, "점근 표기법(Asymptotic Notation)"을 사용한다.
Asymptotic Notation은 수식이 있으므로 다음 글에서...
정리
계산복잡도 이론 : 비슷한 복잡도를 가진 알고리즘끼리 분류하기 위한 이론
시간복잡도 이론 : 알고리즘의 시간적 효율성을 분류해보기 위한 이론
-> 알고리즘에 n개의 데이터를 주었을 때 연산이 일어나는 횟수를 f(n)으로 표시한다.
-> f(n) 같은 수식보다 단순하게 나타내기 위해 점근 표기법(Asymptotic Notation)을 사용한다.
