시간복잡도/ BigO표기법

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다 

---

프로그래머스에서 문제를 풀다보면 종종 시간초과 때문에 문제를 틀리는 경우가 발생한다. 

그렇기 때문에 코드를 짤때엔 시간 복잡도를 고려해주는 것이 중요한 요소이다. 

 

▷시간 복잡도란?

알고리즘이 특정 크기의 입력에 대해 수행하는데 얼마나 오래걸리는 지를 나타내는를 의미한다. 내가 코드를 어떻게 짜느냐에 따라 시간복잡도가 달라지기 때문에 데이터의 입력 크기에 맞춰 적절한 전략을 세워 시간복잡도를 줄이도록 노력하는 것이 중요하다. 

 

▷ 시간복잡도 표현 - bigO 표기법

시간복잡도를 표현하는 방법으로는 bigO표기법이라는 것이 있다. 만일 2N^3 + 1000이라는 다항식이 있다고 할 때 빅오 표기법은 차수가 가장 높은 항만을 고려하여 O(N^3)이라고 시간복잡도를 표기한다. 그렇기 때문에 상수는 거의 무시되는 표기법이라 할 수 있는데 만일 N이 1인 경우 해당 다항식에서 상수의 영향은 크다. 이런 경우를 고려했을 때 빅오표기법은 때에 따라 그리 정확하지 못한 표기법이 될 수 있다는 점을 생각해보아야 한다. 

 

 > O(1) 상수 시간

 > O(logN) 로그 시간

 > O(N) 선형시간

 > O(NlogN) 로그 선형 시간

 > O(N^2) 이차 시간

 > O(N^3) 삼차 시간

 > O(2^n) 지수 시간

 

위에서 아래로 갈수록 시간 복잡도가 증가한다고 생각하면 된다. 

위에서 언급하였듯이 알고리즘에서 어떤 알고리즘을 사용하느냐에 따라 시간복잡도가 달라지는데 알고리즘 마다 항상 최악의 시간복잡도를 고려하여 문제 전략을 짜야한다. 

 

▷ 시간 측정 방법

표준라이브러리에서 time라이브러리를 사용하면 해당 코드의 소요시간을 알 수 있다. 

import time
start= time.time() 
# 시간 측정할 코드 
end= time.time()

print('소요된 시간', end- start)