Summary
- 시간복잡도는 알고리즘을 수행하는 연산의 수이며, 이 값이 낮은 알고리즘을 선택하는 것이 성능에 유리하다.
- 알고리즘의 실행시간에서 가장 중요한 것은 성장률이며, 이를 점근적 표기법(Asymptotic notation)이라 부른다.
- 점근적 표기법 중 최악의 경우를 나타내는 Big-O가 가장 널리 사용된다.
- 실행시간이 아닌 연산 수치로 판별하는 이유는 명령어 실행시간이 하드웨어·언어에 따라 편차가 크기 때문이다.
알고리즘과 시간복잡도
개념
알고리즘은 어떤 목적을 달성하기 위해 거쳐야 하는 일련의 과정이며, 시간복잡도는 알고리즘을 수행하는 연산의 수를 뜻한다. 따라서 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다.
실행시간
알고리즘의 실행시간에서 가장 중요한 것은 성장률이며, 이를 점근적 표기법(Asymptotic notation)이라 부른다.
점근적 표기법
| 표기법 | 경우 | 설명 |
|---|---|---|
| Big- | 최상의 경우 | 오메가 표기법 |
| Big- | 평균의 경우 | 세타 표기법 (정확하지만 까다로움) |
| Big-O | 최악의 경우 | 빅오 표기법 (가장 널리 사용) |
빅오 표기법(Big-O)
빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 하는 것이 목적이다.
- 시간복잡도: 입력된 의 크기에 따라 실행되는 조작의 수
- 공간복잡도: 알고리즘이 실행될 때 사용하는 메모리의 양
표기법은 O(n)과 같이 괄호 안에 표시된다.
시간복잡도의 실제 기준
시간복잡도란 알고리즘의 성능을 설명하는 지표로, 알고리즘을 수행하기 위해 프로세스가 수행해야 하는 연산을 수치화한 값이다.
실행시간이 아닌 연산 수치로 판별하는 이유
명령어의 실행시간은 하드웨어 및 프로그래밍 언어에 따라 편차가 크게 달라진다. 따라서 명령어의 실행 횟수만을 고려한다.
일반적으로 알고리즘 문제에서 경우의 수가 이면 약 1초가 소요된다.
시간 복잡도 기준
= 1억 = 1초
Reference