[Coding Test] 시간 복잡도

Do it! 알고리즘 코딩테스트 with JAVA
인프런 로드맵 - 하루코딩
인프런 로드맵 보기

시간 복잡도

시간 복잡도란?

주어진 문제를 해결하기 위한 연산 횟수

시간 복잡도 유형

1. Ω(n) : Best case 의 연산 횟수를 나타낸 표기법
   
2. Θ(n) : Average case 의 연산 횟수를 나타낸 표기법
   
3. O(n) : Worst case 의 연산 횟수를 나타낸 표기법
   

코딩테스트에서는 Worst case 를 염두해두고 수행 시간을 계산해야 한다.

연산 횟수 계산 방법

연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기

연산 횟수는 1초에 1억 번을 기준으로 생각하면 된다.

예시) 제한 시간 2초

• 버블 정렬 (O(n^2))
  1,000,000^2 = 1,000,000,000,000 > 200,000,000
  –> 부적합

• 병합 정렬 (nlogn)
  1,000,000log(1,000,000) = 20,000,000 <200,000,000
  –> 적합

시간 복잡도를 바탕으로 코드 로직 개선하기

1. 상수는 시간 복잡도 계산에서 제외
2. 가장 많이 중접된 반복문의 수행 횟수가 시간 복잡도의 기준

결론

1. 알맞은 알고리즘 선택
2. 비효율적인 로직 찾아서 효율적으로 개선