[Algorithm] N 의 범위에 따른 시간 복잡도 선택

들어가기 앞서,

• 코딩 테스트에서, 문제의 제한 시간은 일반적으로 1~5초 가량이다.
• 일반적인 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 1초에 실행할 수 있는 연산량은 1억번이다.
• 따라서, 문제를 풀기 전, 문제의 시간 복잡도를 확인한다면, 얼마나 효율적인 알고리즘을 작성해야하는지 눈치 챌 수 있다.
  • 예를 들어, 주어진 N의 범위가 최대 5,000이며, 주어진 제한 시간이 1초라면,
  • 시간 복잡도가 O(N^3)인 알고리즘의 연산 횟수는 10억을 넘어가며, 10초 이상의 시간이 걸리므로, 사용하기 어렵다.

N 의 범위와 시간 복잡도에 따른 연산 횟수

• N 의 범위가 1,000 일 경우
  • O(N) : 1,000
  • O(NlogN) : 10,000
  • O(N^2) : 1,000,000
  • O(N^3) : 1,000,000,000
• 즉, N 의 범위가 1,000 일 경우, 시간 복잡도가 O(N^2) 이하인 알고리즘을 설계하는게 좋다.

제한 시간이 1초 일 경우, N 의 범위에 따른 시간 복잡도 선택

• N 의 범위가 500 인 경우
  • 시간 복잡도가 O(N^3) 이하인 알고리즘을 설계
• N 의 범위가 2,000 인 경우
  • 시간 복잡도가 O(N^2) 이하인 알고리즘을 설계
• N 의 범위가 100,000 인 경우
  • 시간 복잡도가 O(NlogN) 이하인 알고리즘을 설계
• N 의 범위가 10,000,000 인 경우
  • 시간 복잡도가 O(N) 이하인 알고리즘을 설계
• N 의 범위가 10,000,000,000 인 경우
  • 시간 복잡도가 O(logN) 이하인 알고리즘을 설계

참고

• 이것이 취업을 위한 코딩 테스트다. with python