[Algorithm] 기본적인 알고리즘 분석 방법

빅 O 표기법( Big O notation )

    어떤 알고리즘이 처리할 자료집합의 크기가 커짐에 따라 알고리즘의 효율이 어떻게 변화하는지를 대략적으로 추정하는 함수

O( 함수 ) 의 형태로 표기한다.

점근적 상한을 나타낸다.

 

복잡도 

    낮은 것에서 높은 순으로 나열하면

    상수 < log₂ N < N < Nlog₂N <  N² < N³ < 2ⁿ 이다.

    복잡도가 낮을수록 빠르다.

 

O ( c )  - 상수

    자료집합에 크기와 상관없이 항상 동일하다는 의미이다. 가장 빠른 것으로 간주된다.

O ( log₂N, )

    자료집합의 크기에 의존하는 알고리즘 중에서는 가장 효율적인 알고리즘이다.

    데이터가 적을 때는 비효율적일 수 있으나 자료집합이 커질수록 효율적이게 된다

O ( n ) 

    자료집합의 크기가 증가함에 따라 일정한 비율로 시간이 증가한다.

O( n log₂N )

    일반적으로 정렬알고리즘이 가져야 할 최소한의 복잡도

    이 정도면 비교적 효율적이라고 간주한다.

O( N² )

    자료집합의 크기가 증가함에 따라 소요시간이 급격히 증가하게 된다.

    비효율적인 알고리즘, 2중 for문이 대표적이다.

O( N³ ) 

    N² 보다도 더 안좋은 알고리즘.

O( 2ⁿ )

    매우 안좋은 알고리즘. 사용하지 말자.