[코딩 테스트] 복잡도의 개념 (시간 복잡도 / 공간 복잡도)

코테 문제를 풀다보면 "복잡도"라는 개념을 만나게 된다. 알고리즘 문제를 풀때는 보통 시간 복잡도를 의미한다.

프로그래머스를 통해 문제를 풀다보면 몇개의 테스트 케이스에서 시간 제한을 넘겨 통과하지 못한 적이 종종 있었다. 그래서 우선 시간 복잡도에 대한 개념을 정리해보고자 한다.

 

복잡도의 종류

• 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘
• trade-off 관계

시간 복잡도 

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미 
• 알고리즘을 위해 필요한 연산의 횟수

공간 복잡도 

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 
• 알고리즘을 위해 필요한 메모리의 양 

 

---

표현 방식

빅오 표기법	명칭
$O(1)$	상수 시간
$O(logN)$	로그 시간
$O(N)$	선형 시간
$O(NlogN)$	로그 선형 시간
$O(N^2)$	이차 시간
$O(N^3)$	삼차 시간
$O(2^n)$	지수 시간

• 해당 표의 위쪽에 있을 수록 더 빠름
• 일반적인 코테에서  $O(N^3)$ 시간 복잡도를 넘어가면 사용하기 어려움 
• 데이터의 개수가 N= 1,000이면 $O(N)$ = 1,000 , $O(N^2)$ = 1,000,000 을 의마함
• 문제에서 제시된 N의 범위가 클수록 시간 복잡도가 낮은, 빠른 속도를 가지는 알고리즘을 구현해야 함.

---

시간 복잡도 계산하기 

import time #시간 계산하는 라이브러리
start = time.time() #측정 시작

##--- 시간 측정할 코드 -----

end = time.time()
print("time:" , end-start)

time 라이브러리를 사용하면 실행할 시간을 간단하게 확인할 수 있다. 해당 라이브러리는 평소에 코드 작업 시 시간 확인에도 많이 사용하던 라이브러리였다. 

 

[reference]

도서 "이것이 코딩 테스트다" (https://github.com/ndb796/python-for-coding-test)