알고리즘 성능평가(복잡도)

복잡도(Complexity)

알고리증 성능을 나타내는 척도.

 

시간복잡도 : 입력에대한 알고리즘의 수행시간 분석

공간복잡도 : 입력에대한 알고리즘의 메모리 사용량 분석

 

시간 복잡도가 높다는것은 알고리즘의 수행시간이 높은것을 나타낸다.

시간 복잡도가 낮다는것은 알고리즘의 수행시간이 낮은것을 나타낸다.

따라서 같은 기능을 수행하는 알고리즘에 대해서는 시간복잡도가 낮을수록 품질이 좋다.

 

 

---

시간복잡도의 표기법

 

빅오 표기법(Big-O Notation)

가장 빠르게 증가하는 항만을 고려하는 표기법 : 함수의 상한만을 나타낸다.

예를 들어 연산횟수가 3N^3 + 15^2 +15520 인 알고리즘이 있다고 했을경우 빅오표기법으로는 O(N^3)으로 표기됩니다.

N의 값이 아주 큰 수라고했을경우 나머지 연산횟수는 비교적 작은값이 되기때문에 가장 큰 항만을 표기한다.

순위	명칭
O(1)	상수기간(Constant time)
O(logN)	로그시간(Log time)
O(N)	선형시간
O(Nlog^N)	로그 선형시간
O(N^2)	이차 시간
O(N^3)	삼차시간
O(2^n)	지수시간

---

var array = [1,2,3,4,5];

var sum=0;

array.forEach(value=>{

sum+=value;

});

해당 알고리즘이 있을경우 array의 시간복잡도는 O(N)이다.

---

var array = [1,2,3,4,5];

var sum=0;

 

array.forEach(x=>{

    array.forEach(y=>{

        sum+=x*y;

    });

});

해당 알고리즘의 경우에는 시간복잡도가 O(N^2)이다.

하지만 모든 2중반복문의 시간복잡도가 O(N^2)인것은 아니다.

내부적으로 처리시 break; 처리를 한다던지 다른 솔루션이 있다면 시간복잡도는 달라질 수 있다.