Summary
- 시간복잡도는 알고리즘을 수행하는 연산의 수이며, 이 값이 낮은 알고리즘을 선택하는 것이 성능에 유리하다.
- 알고리즘의 실행시간에서 가장 중요한 것은 성장률이며, 이를 점근적 표기법(Asymptotic notation)이라 부른다.
- 점근적 표기법 중 최악의 경우를 나타내는 Big-O가 가장 널리 사용된다.
- 실행시간이 아닌 연산 수치로 판별하는 이유는 명령어 실행시간이 하드웨어·언어에 따라 편차가 크기 때문이다.
알고리즘과 시간복잡도
개념
알고리즘은 어떤 목적을 달성하기 위해 거쳐야 하는 일련의 과정이다. 시간복잡도는 알고리즘을 수행하는 연산의 수를 뜻한다. 따라서 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다.
실행시간
시간복잡도와 관계있는 알고리즘의 실행시간은 컴퓨터가 코드를 실행하는 속도에 의존한다. 가장 중요한 것은 성장률이다.
함수의 입력값 크기에 따라 증가하는 함수량을 성장률이라고 한다. 중요하지 않은 상수와 계수를 제거하면 성장률 계산에 집중할 수 있다. 이를 점근적 표기법(Asymptotic notation)이라고 하며, 가장 영향이 큰 항만 계산한다는 의미다.
점근적 표기법
시간복잡도를 나타낼 때 사용하는 점근적 표기법은 3가지가 있지만, 평가하기 쉬운 최악의 경우인 빅오 표기법(Big-O) 을 가장 널리 사용한다.
| 표기법 | 경우 | 설명 |
|---|---|---|
| Big- | 최상의 경우 | 오메가 표기법 |
| Big- | 평균의 경우 | 세타 표기법 (정확하지만 까다로움) |
| Big-O | 최악의 경우 | 빅오 표기법 (가장 널리 사용) |
빅오 표기법
다시 말해, 빅오 표기법은 점근적 상한에 대한 표기법으로 최악의 경우 계산되는 계산량을 의미하며 이를 통해 불필요한 연산을 제거하여 컴퓨터가 알고리즘 분석을 쉽게 하도록 한다.
빅오 표기법에서 측정하는 복잡성의 종류는 시간과 공간복잡도가 존재한다.
- 시간복잡도: 입력된 의 크기에 따라 실행되는 조작의 수
- 공간복잡도: 알고리즘이 실행될 때 사용하는 메모리의 양
그림. Big-O 복잡도 (출처: Algorithms: Big O Notations)
시간복잡도
시간복잡도는 알고리즘의 성능을 설명하는 지표로 알고리즘에서 수행하는 프로세스의 연산을 수치화한 것이다.
실행시간이 아닌 연산수치가 기준인 이유
- 명령어 실행시간은 하드웨어 및 프로그래밍 언어에 따라 편차가 크게 다름
- 따라서, 실행시간이 아닌 명령어의 실행 횟수(연산수치)만을 고려
시간복잡도에서 가장 중요한 것은 입력값인 N의 단위이다.
예를 들어, 25 * N^2 + 2*N + k 일 때 빅오 표기법에 따라 O(25 * N^2 + 2*N + k)로 표기할 수 있다. 2*N + k는 25*N^2에 비해 상대적으로 작은 차수로써 계산량에서 제외한다. 즉, 최고 차수만 남는다고 생각하면 된다.
시간복잡도는 함수의 입력(N)에 따른 계산량임을 참고하여 해당 연산의 시간 복잡도를 빅오 표기법으로 나타내면 O(N^2) 이 된다.
| 시간복잡도 | 한글명 | 문제 해결 단계 수 |
|---|---|---|
O(1) | 상수 시간 | 오직 한 단계 |
O(log N) | 로그 시간 | 특정 요인에 의해 감소 |
O(N) | 직선적 시간 | 입력값과 1:1 |
O(N * log N) | 선형로그 시간 | N * logN 만큼 수행시간 가짐 |
O(N^2) | 2차 시간 | 입력값의 제곱 |
O(C^N) | 지수 시간 | 주어진 상수의 입력값 제곱 |
일반적으로 알고리즘 문제에서 경우의 수가 (1억)이면 시간 복잡도 기준으로 약 1초가 소요된다.
Reference