시간 복잡도와 공간 복잡도

시간 복잡도

- 알고리즘을 수행하는 동안 연산이 몇번이나 수행되는지를 나타내는 것 ( 수행 시간 분석 )

- 빅-오 표기법 개념 이용

 

공간 복잡도

- 프로그램을 실행 시키고 나서 완료하는데 필요한 저장 공간의 양을 나타내는 것 ( 메모리 사용량 분석 )

- 빅-오 표기법 개념 이용

 

https://thecodingbay.com/learn-everything-about-big-o-notation/

O(1) (Constant)

-> 입력되는 값의 크기와 상관없이 항상 일정한 시간이 걸림

-> Stack

 

O(logn) (Logarithmic)

-> 입력되는 값의 크기가 커질수록 처리 시간이 logn 만큼 짧아짐

-> Binary-Tree

 

O(n) (Linear)

-> 입력되는 값의 크기가 커질수록 같이 비례해서 처리 시간이 증가

-> For

 

O(nlogn) (Linear-Logarithmic)

-> 입력되는 값의 크기가 커질수록 처리시간은 로그값 만큼 비례해서 증가

-> Sort

 

O(n^2) (Quadratic)

-> 입력되는 값의 크기가 커질수록 처리시간이 엄청나게 증가

-> Fibonacci sequence

 

O(2^n) (Exponential)

-> 입력되는 값의 크기가 커질수록 기하급수적으로 증가

 

즉, 처리속도가 빠를 수록 좋다 ( 물론 상황에 따라서 다름 )