시간 복잡도

[Do it! 알고리즘 코딩 테스트]

 

최근에 백준 문제 푸는거에 재미를 붙였다. 지금 실버1인데 올해 안에 골드 1이 되겠다는 목표로 열심히 풀어보고자 한다.

지금 실력으로는 문제를 보면서 어떤 알고리즘을 써야 하는지 바로 떠올리기가 힘들다. 그래서 알고리즘 공부를 찬찬히 하면서 실력을 기르려고 한다. 이 책을 2주 안에 끝낼 것이다!

 

---

시간 복잡도

어떤 알고리즘을 써서 문제를 풀어야 할지를 결정하는데 시간 복잡도가 중요하다. 

일반적으로 파이썬은 1초에 2000만~1억 번 연산을 한다.

최악의 경우를 따져봐야 하기 때문에 파이썬이 1초에 2000만 번 연산을 한다고 생각하고 계산하자.

 

예를 들어 수를 정렬하는 문제가 있다.

시간 제한은 2초이고, 수의 개수 N(1<=N<=1,000,000)이다.

시간 제한이 2초이기 때문에 4000만 번의 연산이 가능하다.

 

정렬 알고리즘은 버블, 선택, 삽입, 퀵, 병합, 힙 등 굉장히 많은데 각 알고리즘의 시간 복잡도는 다르다.

버블은 O(n^2), 병합은 O(nlogn)의 시간복잡도를 가진다.

버블 정렬을 했을 때 1,000,000^2 = 1,000,000,000,000의 연산이 필요하다.  > 400,000,000 

병합 정렬을 했을 때 1,000,000log(1,000,000) = 약 20,000,000의 연산이 필요하다. < 40,000,000

따라서 버블 정렬은 적합하지 않고, 병합 정렬이 적합한 알고리즘이라는 것을 알 수 있다.

 

기억하기

• 파이썬은 1초에 2000만 번 연산을 한다.
• 가장 많이 중첩된 반복문의 수행 횟수로 시간 복잡도를 구하자.