[자료구조] 2. 알고리즘 성능 분석 - 시간 복잡도 분석 / 빅오 표기법
알고리즘 성능 평가 지표
시간 복잡도 분석이란?
1) 시간 복잡도 함수
2) 알고리즘 효율성의 세 가지 경우
빅오란?
1) 빅오의 수학적 판별법
2) 간단하게 빅오를 구하는 방법
3) 대표적인 빅오
알고리즘의 성능은 '속도'와 '메모리의 사용량' 이렇게 두 가지 지표로 평가된다.
시간 복잡도 : 속도에 해당하는 알고리즘의 수행 시간 분석 결과.
공간 복잡도 : 메모리 사용량에 대한 분석 결과.
일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행 속도에 초점을 둔다.
2.1 시간 복잡도 분석 방법
알고리즘을 이루고 있는 연산의 횟수를 세는 방법.
직접 구현하지 않고도 모든 입력을 고려하는 방법이고 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.
1) 시간 복잡도 함수
시간 복잡도 함수 : 처리해야 할 데이터의수 n에 대한 연산 횟수의 함수.
시간 복잡도 함수식T(n)을 구성하면 데이터 수의 증가에 따른 연산 횟수의 변화 정도를 판단할 수 있다.
(그래프를 통해 데이터 수의 변화에 따른 연산 횟수의 변화 정도를 한눈에 파악할 수 있고, 이것을 통해 둘 이상의 알고리즘을 비교하기가 용이해진다.)
[시간 복잡도 함수 구성 방법]
연산 횟수를 대표하는 연산(다른 연산들이 이 연산에 의존적임)을 대상으로 시간 복잡도를 구한다.
시간복잡도 함수는 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단하는 것이 목적이므로 함수식을 구성할 때 데이터 수 n의 증가와 무관한 연산 부분은 무시해도 된다.
* 데이터의 수가 적은 경우보다 데이터의 수가 많아짐에 따른 연산 횟수 증가 정도가 중요하다.
2) 주어지는 자료 집합에 따른 알고리즘 효율성의 경우
최선의 경우(best case)
평균적인 경우(average case)
최악의 경우(worst case)
데이터의 수가 많아지면 알고리즘 별로 최악의 경우에 수행하게 되는 연산의 횟수가 큰 차이를 보인다. 따라서 최악이 경우의 수행시간이 알고리즘의 시간 복잡도 척도로 많이 쓰인다.
2.2 빅오 표기법(Big O Notation)
빅-오 : 시간 복잡도 함수 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것.
데이터 수의 증가에 따른 연산 횟수의 증가 형태를 표현한 것.
데이터 수의 증가에 따른 연산 횟수 증가율의 상한선을 표현한 것.
빅오 표기법에서는 데이터 수 n의 증가와 무관한 연산 부분뿐만 아니라 n의 증가와 연관되지만 미치는 영향이 상대적으로 미미한 연산 부분도 무시한다. 즉, 가장 큰 영향을 미치는 연산만을 고려한다.
- 예시 -
T(n) = n² + 2n +1 이 식에서 n이 증가함에 따라 2n+1 이 미치는 영향은 미미해지므로
T(n) = n² 으로 간략화 할 수 있다.
이것을 빅오 표기법으로 표현하면 다음과 같으며, "빅오 오브 n²(Big-O of n²)" 이라고 읽는다.
O(n²)
결론적으로 시간 복잡도 함수 T(n) = n² + 2n +1 에서 빅오는 n² 이며,
이것은 n의 증가 및 감소에 따른 T(n)의 변화 정도가 n² 형태를 띰을 의미한다.
1) 빅오의 수학적 판별법
두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n ≥ K에 대하여 f(n) ≤ Cg(n)을 만족하는 두 개의 상수 C와 K가 존재한다면,
f(n)의 빅오는 O(g(n))이다.
2) 간단하게 빅오를 구하는 방법
시간 복잡도 함수가 다항식으로 표현 된 경우, 최고차항의 차수가 빅오 빅오가 된다.
- 예시 -
T(n) = 4n³ +2n² + n +1 => O(n³)
* log n도 차수를 가지기 때문에 간략화하면 안 된다.
T(n) = 4n³log n + 2n² + n +1 => O(n³log n)
3) 대표적인 빅오
성능(수행시간, 연산횟수)이 좋은 순서대로
- O(1) : 상수형 빅오 - 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘
- O(log n) : 로그형 빅오 - 데이터 수의 증가율에 비해 연산 횟수의 증가율이 훨씬 낮은 알고리즘 (매우 바람직) * 로그의 밑은 무시한다.
- O(n) : 선형 빅오 - 데이터의 수와 연산 횟수가 비례하는 알고리즘
- O(nlog n) : 선형로그형 빅오 - 데이터의 수가 두 배로 늘 때, 연산 횟수는 두 배를 조금 넘게 증가하는 알고리즘
- O(n²) : 2차형 빅오 - 데이터 수의 제곱에 해당하는 연산 횟수를 요구하는 알고리즘 * 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우
- O(n³) : 3차형 빅오 - 데이터 수의 세 제곱에 해당하는 연산 횟수를 요구하는 알고리즘
- O(2ⁿ) : 지수형 빅오 - 엄청난 연산 횟수의 증가로 인해 사용하기에는 매우 무리가 있고 비현실적인 알고리즘
