알고리즘 문제에서의 시간 복잡도(빅오 표기법)

빅오 표기법 사용

ex) O(N)

Big O

g(n)<=c*f(n):asymptotic upper bound

(c:some positive real constant N:some nonnegative integer s.t. for all n>=N)

g(n) is big O of f(n)

시간 복잡도를 계산할 때 상수는 버리며 가장 차수가 큰 변수를 기준으로 한다.

ex) n^2 와 n이 있을 경우 n^2이 빅오 표기법에 사용됨.

 

시간복잡도와 달리 공간 복잡도는 알고리즘 문제에서 크게 상관이 없는 경우가 많지만

필요없는 공간을 사용하고 있진않은지 신경을 쓸 필요는 있다.