[C++ / Algorithm] 시간 복잡도란? #2
1. 알고리즘의 효율성
알고리즘은 문제를 해결하였는지 뿐만이 아니라 그 문제를 해결하는 데 걸린 시간도 중요하게 생각한다.
따라서 시간 복잡도는 해당 알고리즘이 어느정도의 효율을 가졌는지를 분류하는 기준이다.
2. 시간 복잡도의 종류
시간 복잡도는 크게 3가지로 나눌 수 있다.
- Big-O 표기법
- Big-Ω 표기법
- Big-θ 표기법
2-1. Big-O(빅-오) 표기법
빅-오 표기법은 수행 시간이 최악인 경우를 표기하는 표기법으로
해당 알고리즘이 최대 얼마나 느리게 실행되는지 알기에 적합 합니다.
또한 가장 많이 쓰이는 표기법입니다.
2-2. Big-Ω(빅-오메가) 표기법
빅-오메가 표기법은 수행 시간이 최적인 경우를 표기하는 표기법으로
해당 알고리즘이 최소 얼마나 빠르게 실행되는지 알기에 적합 합니다.
2-2. Big-θ(빅-세타) 표기법
빅-세타 표기법은 빅-오 표기법과 빅-오메가 표기법의 평균으로
해당 알고리즘 실행시간의 최상과 최악을 판별하기에 적합 합니다.
3. Big-O(빅-오) 표기법이란?
빅-오 표기법은 O 뒤에 소괄호를 열고 증가 함수를 넣어주면 됩니다.
예를 들어, N개의 입력 데이터를 받는 알고리즘 A가 총 N번의 연산을 했다면,
알고리즘 A의 시간 복잡도는 빅-오 표기법으로 O(N)이 되는 것입니다.
시간 복잡도 표기법은 실행 시간에 크게 영향을 주지 않는 요소는 제거하는 것이 특징입니다.
따라서 N개의 데이터를 3N + 3번의 연산으로 처리했더라도 `O(N)이라고 표기합니다.
3-1. O(1)
O(1)은 입력 데이터의 상관 없이 최악의 경우에도 상수 시간 안에 종료된다는 의미입니다.
3-2. O(log N)
O(log N)은 입력 데이터가 증가하는 속도보다 수행 시간이 천천히 증가하는 알고리즘을 의미합니다.
3-3. O(N)
O(N)은 입력 데이터가 증가하는 속도와 실행 속도가 비례하게 증가하는 알고리즘을 의미합니다.
3-4. O(N log N)
O(N log N)은 입력 데이터가 증가하는 속도보다 수행 시간이 훨씬 빠르게 증가하는 알고리즘을 의미합니다.
3-5. O(N^2)
O(N^2)은 최악의 경우 입력 데이터 N의 제곱만큼 실행 시간이 늘어납니다. N회 반복하는 반복문이 2개 중첩되어 있으면 이와 같은 성능이 나옵니다.