[알고리즘] 시간 제한과 시간 복잡도

Janet·2023년 10월 3일
2

Algorithm

목록 보기
257/314
post-thumbnail

시간 제한과 시간 복잡도

  • 코딩 테스트에서 문제의 제한 시간은 보통 1~5초 정도이다.
  • 일반적인 CPU 기반의 PC나 채점용 컴퓨터에서 1초에 실행할 수 있는 최대 연산 횟수는 약 1억번이다.
  • 따라서 문제를 풀 때 먼저 시간 복잡도를 확인하여 어떤 알고리즘을 써서 코딩을 해야할지 가늠을 할 수 있다.

    ex) 문제에서 주어진 N의 최대값이 10만이며, 주어진 제한 시간은 1초라면?

    시간 복잡도가 O(N^2)인 알고리즘의 연산 횟수는 10만번*10만번 = 100억번이므로 사용할 수 없다.

1초에 최대 연산 횟수(최대 입력 크기)

시간 복잡도최대 연산 횟수
O(N)약 1억번
O(N^2)약 1만번
O(N^3)약 500번
O(2^N)약 20번
O(N!)10번

제한 시간이 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) 이하인 알고리즘을 설계

Reference.

  • 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈 저
profile
😸

0개의 댓글