시간 복잡도 빠르게 알아내기

아무것도 못풀었는데 벌써...?

 

코딩 인터뷰 문제를 풀면서 테스트 케이스는 통과해도, 시간 초과로 통과하지 못해 좌절해본 경험이 있는가? 어떻게든 실행시간을 줄여보려고 코드를 튜닝하지만 제한된 시간의 압박과 초조함이 코드를 더 엉망으로 만든다. 코드를 쓰기 전에 내 알고리즘의 성능을 대략적으로 판단할 수 있다면 이런 불상사를 막을 수 있을 것이다. 이번 포스팅에서는 시간 복잡도를 빠르게 판단할 수 있는 방법을 정리한다. 순서대로 내 알고리즘에 적용해보자.

 

 

---

 

 

1. 반복문

 

가장 먼저 봐야할 부분은 반복문이다. 반복문이 몇 번 중첩되어 있는지부터 확인해보자. 중첩되어 있지 않은 반복문은 심플하게 N회를 순회하니까 O(N)이라고 판단할 수 있을 것이다. N번을 반복하는 반복문이 한 번 중첩되어 있다면 N * N회, O(N^2)이라고 판단할 수 있다. 반복문을 가장 먼저 확인하면서 시간 복잡도를 알아내자.

 

 

2.  주먹구구 법칙

 

반복문 기준으로 점근적인 시간복잡도를 얻어냈다면 밑의 법칙에 따라 판단해보자.

 

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억을 넘어가면 시간제한을 초과할 가능성이 있다.

 

시간제한이 8초인 문제가 있고, N의 크기가 100,000이라고 가정하자. 현재 내 알고리즘의 시간복잡도가 O(N^2)이라고 가정하면 시간제한을 초과할 가능성이 있을까? 반복 회수는 (10^10 / 8) 이므로 알고리즘을 다시 설계해야 한다!

 

 

---

 

 

두 단계의 간단한 법칙만으로 내 알고리즘의 문제를 파악할 수 있다. 코드를 작성하기 전에 알고리즘 설계 단계에서 대략적인 내 코드의 성능을 파악할 수 있다면 코딩 인터뷰에서 코드 튜닝으로 인한 많은 시간 손실을 막을 수 있을 것이다.  코드를 작성하기 전에 알고리즘 설계를 먼저 하면서 문제를 접근하도록 하자!

 

 

 

Reference

알고리즘 문제 해결 전략 - 구종만