복잡도(Complexity)란?
복잡도라고 말하면 이름 그대로 정말 복잡해 보이지만 그냥 어떤 알고리즘이 효율적인지를 판단하는 척도
알고리즘의 성능과 효율성을 나타내는 기준.
크게 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다.
알고리즘에 주어진 입력T(n)을 기준으로 수행시간 혹은 메모리 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다.
복잡도를 나타내는 방법으로는 점근 표기법으로 O(빅오), Ω(오메가), Θ(세타) 등이 있고, 주로 빅오와 세타 표기법이 많이 사용된다.
시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)
시간 복잡도(Time Complexity): 수행시간 분석결과
공간 복잡도(Space Complexity): 메모리 사용량에 대한 분석결과
메모리를 적게 쓰고 속도도 빨라야 최적의 알고리즘이라 할 수 있다. 그런데 일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 둔다. 대개는 속도에 관심이 더 많고, 또 중요한 요소로 판단되기 때문이다. 물론 특정 알고리즘에 대해서 상대적인 우월성을 입증해야 하는 경우에는 메모리의 사용량도 함께 고려가 되지만, 이미 검증이 끝난 알고리즘의 적용을 고려하는 경우에는 속도에 초점을 두어 적합성 여부를 판단하게 된다.
알고리즘의 속도 평가
처리해야할 데이터수에 대한 연산 횟수
데이터의 수 n에 대한 연산회수의 함수 T(n)을 구성한다.
알고리즘의 복잡도 계산하기
복잡도를 계산할때 최선의 경우(best case)는 고려하지 않는다. 최악의 경우(worst case), 평균적인 경우(average case)만 계산한다. 알고리즘에서는 최악의 경우를 기준으로 하는게 일반적이다.
최악의 경우( worst case)
데이터의 수가 n개일 때, 최악의 경우는 마지막 까지(n까지) 연산하는 것이다.
평균적인 경우(average case)
가정1: 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정한다.
가정2: 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률은 동일하다.
위 두가정을 근거로 계산을 해본다면
* 탐색 대상이 존재하지 않는 경우의 연산횟수 n
* 탐색 대상이 존재하는 경우의 연산횟수 n/2
두경우를 하나로 묶으면
(n * 1/2) + (n/2 * 1/2) = 3/4n
=> T(n) = 3/4n
평균적인 경우의 시간 복잡도 함수는 신뢰도가 높지 않다. 두 개의 가정을 뒷받침할 근거가 부족하기 때문이다. 프로그램의 성격에 따라서 그리고 데이터의 성격에 따라서 배열에 탐색 대상이 존재할 확률은 50%보다 높을 수도 있고 높지 않을 수도 있는데 이러한 부분이 전혀 고려되지 않았다. 때문에 우리가 계산한 평균적인 경우의 시간 복잡도는 '최악의 경우'의 시간 복잡도보다 신뢰도가 낮다.
빅-오 표기법(Big-Oh Notation)
함수 T(n)에서 영향력이 가장 큰 부분이 어느 부분인가를 따지는 것
예를 들면 T(n) = n + 1 라면 빅오는 O(n) 이된다.
T(n) = 3n^2 + 2n + 1 이라면 빅오는 O(n^2)가 된다.
T(n)이 다항식으로 표현이 된 경우, 최고차항의 차수가 빅-오가 된다.
빅-오는 데이터 수의 증가에 따른 연산횟수의 증가 형태(패턴)을 나타내는 표기법이므로
최고차항의 수(3), 나머지 항, 상수 도 무시한다. 딱 최고차항의 차수만 표기한다.
대표적인 빅-오
| O(1) | 상수형 빅-오. 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 뜻한다. 예를 들어 3회 진행되는 알고리즘일지라도 O(3)이 아니라 O(1)로 표기한다. |
| O(log n) | 로그형 빅-오. 데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘을 의미한다. 매우 바람직한 유형이다. |
| O(n) | 선형 빅-오. 데이터의 수와 연산횟수가 비례하는 알고리즘 유형이다. |
| O(n * log n) | 선형 로그형 빅-오. 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘을 의미한다. n과 log n을 곱한 형태라서 난해해 보이지만, 알고리즘 중에는 이에 해당하는 알고리즘이 적지 않다. |
| O(n^2) | 제곱에 해당하는 연산횟수를 요구하는 알고리즘. 데이터의 양이 많은 경우에는 적용하기가 부적절한데, 이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 달리 말하면 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다고 할 수 있다. |
| O(n^3) | 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘. 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생. 적용하기에는 무리가 있는 알고리즘이다. |
| O(2^n) | 지수형. 사용하기에 매우 무리가 있는, 사용한다는 것 자체가 비현실적인 알고리즘. 지수적 증가라는, 매우 무서운 연산횟수의 증가를 보이기 때문이다. 처음 알고리즘을 개발했을 때 이러한 성능을 보인다면, 개선의 과정을 거쳐서 현실적인 연산횟수를 보이는 알고리즘으로 수정 되어야 한다. |
O(1) < O(log n) < O(n) < O( n * log n) < O(n^2) < O(n^3) < O(2^n)
