알고리즘 분석 기준

1. 공간 복잡도 : 알고리즘 실행에 필요한 저장공간의 정도

2. 시간 복잡도 : 알고리즘 실행에 필요한 시간의 정도

 

일반적으로 공간보다 시간에 예민한 환경이 많기 때문에 시간 복잡도를 주로 사용.

 

시간 복잡도에는 두가지 유형이 있다

a. 실제 걸리는 시간 측정

b. 실행되는 명령문의 개수 계산

c. 빅오(big o)계산법

 

빅오계산법은 명령문 계산 함수에서 가장 큰 영향을 주는 항만 남기고 모두 무시한 다음,

그 항의 계수마저 제거하여 남은 것으로 복잡도를 측정하는 것이다.

 

이 예시는 명령문의 개수가 3n+2이다

예를 들어 실행되는 명령문의 개수가 3n+2인 알고리즘이 있다하면,

여기서 가장 큰 영향을 주는 항은 3n이고

계수인 3을 제거해 이 알고리즘의 빅오계산은 O(n)이다.

 

이때 빅오 계산은 n에 들어가는 수의 형태에 따라 크기가 달라진다

상수<로그<1차식(선형)<선형로그(nlogn)<2차(n제곱)<3차(n세제곱)<지수<계승(팩토리얼)