시간복잡도

 

✅  코딩테스트 시간복잡도 

코딩테스트를 보다보면 시간제한을 보게된다. 문제가 정답을 도출하는 것도 중요하지만 주어진 시간에 맞게 문제를 풀어야한다. 

 

ex) 시간제한 :2 초 

 

보통 1초는 1억번 정도라고 생각하면 편하다. 

 

 

1억 (100,000,000 = 10^8 ) → 1초 (10의 8승 상수제외!)
10억 = 1,000,000,000 = 10^9 (콤마(,)가 3개 있는 수치)

 

참고로 int는 4byte로 -2,147,483,648~ 2,147,483,647 범위이며,

(only 양수) 크기로 보면 "21억"이며

for문으로 탐색한다면 21초 소요되는 것을 어림짐작 할 수 있다.

 

 

빅오메가 - 최선일 때

빅세타 - 보통  

빅오 - 최악일 때 

코딩테스트에서는 빅오 기준으로 생각하면 된다. (여러개의 테스트 케이스가 있을 거니까.)

 

 

 

✅  시간복잡도 계산방식 

https://velog.io/@hyunsoo730/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B3%84-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

 

 

 

※ N = 1억이라고 했을 때, 실행시간은 아래와 같다.

https://zoosso.tistory.com/883

 

 

위 기준이 절대적이지는 않고 대략적인 기준이라고 생각하고 사용해야한다. 

 

 

 

✅  참고 

https://zoosso.tistory.com/883