시간복잡도와 공간복잡도

복잡도 계산은 다양한 알고리즘 중에 가장 좋은 알고리즘을 분석하기 위해

사용한다.

좋은 알고리즘이란 가장 시간과 자원을 적게 소모하는 알고리즘이라 할 수 있다.

 

시간복잡도 :  알고리즘을 실행하는 속도.

공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

 

시간복잡도의 주 요소 : 반복문이다.

 

성능 표기법 : 빅 오 표기법(최악), 오메가 표기법(최상), 세타 표기법(평균)

빅오를 가장 많이 쓰는 이유 : 최악의 상황에도 이정도 성능은 보장한다는 의미

 

O(입력)으로 표기,

O(1)->O(logN)->O(N)->O(NlogN)->O(N^2)->O(2^n)->O(n!) 순.

1초 = 반복문으로 1억번 정도 연산시 

가장 높은 차수를 표시한다. ex) n^2+2n  -> O(n^2)