시간 복잡도

하나의 문제를 풀어도 방법은 다양할 수 있다.

다양한 풀이 중 어떤 알고리즘이 더 효율적인지 분석하기 위해 필요하다.

 

공간 복잡도 : 과거엔 메모리 사이즈가 제한적이라 썼었지만 현재엔 메모리 사이즈가 충분하여 거의 사용하지 않는다.

 

성능표기방법

-Big O(빅-오) 표기법 : O(N)

--가장많이 일반적으로 사용

--아무리 최악이라도 이 정도의 성능은 보장한다는 의미

 

-Ω(오메가) 표기법 : Ω(N)

--최상의 실행시간 표기

 

-θ(세타) 표기법 : θ(N)

--평균 실행 속도 표기

 

Big O 표기법

-표현식에 가장 영향을 끼치는 n의 단위로 표기(예. 2n제곱+n -> O(n제곱)

9(상수회) -> O(1)

n+10, 3n+1 -> O(n)

n제곱, n제곱+10, 5n제곱+11 -> O(n제곱)