알고리즘의 복잡도(Complexities)

✔ 알고리즘의 복잡도

크게 공간 복잡도와 시간 복잡도 두 가지로 나눌 수 있습니다. 서로 Trade-off 관계가 있습니다. 공간 복잡도는 메모리를 얼마나 사용하냐에 대한 것이고, 시간 복잡도는 얼마나 많은 일을 하냐에 대한 것입니다. 알고리즘의 Complexity가 높을수록 알고리즘을 구동하는 데에 더 많은 비용이 듭니다.

✔ 공간 복잡도

알고리즘이 동작하기 위해 필요한 공간, 즉 메모리의 크기와 관련있습니다. 많은 경우, 연산의 중간 결과를 저장하기 위해 메모리를 소비합니다. 중간 결과를 저장해서 중복 연산을 줄일 수 있습니다.

✔ 시간 복잡도

알고리즘이 동작하는 데에 걸리는 시간 또는 연산의 횟수와 관련있습니다. 환경에 따라서 소비되는 시간이 다를 수 있기 때문에 연산의 횟수로 비교하는 것이 좀 더 정확합니다.

✔ 복잡도 계산 방법

측정하는 방법과 분석하는 방법이 있습니다.

 

측정 -> 알고리즘을 구동하면서 기초 연산의 횟수를 카운팅하여 측정할 수 있습니다.

let count = 0;
const array = [1, 6, 2, 5, 4, 2, 5, 2, 3, 6, 3];

let sum = 0;
for(let i = 0; i < array.length; i++) {
    count++;
    sum += array[i];
    count++;
    count++;
}
count++;
console.log(sum);

console.log(count);

분석 -> 반복문과 조건문을 고려하여 분기별로 실행 횟수를 분석을 통해 알아낼 수 있습니다.

분석

분석 방식은 복잡도를 눈으로 보여줄 수 있고, 자료구조가 어떻게 되는지 생각하기도 쉽습니다.

✔ 복잡도의 종류

알고리즘 동작 상황은 3가지로 구분할 수 있습니다. 최악의 경우, 최선의 경우, 평균적인 경우로 구분할 수 있습니다.

 

일반적으로 최악의 경우에 대해 알고리즘 복잡도를 정의합니다.

✔ Asymptotic Notations

점진적 표기 방법입니다. 알고리즘에 입력되는 자료의 개수가 충분히 많다고 가정할 때, 성능 평가에 공평한 비교를 하기 위한 성능 분석 기준으로 사용합니다.

---

※ 참조

강사 신제용, 패스트캠퍼스 자료구조와 알고리즘 강의