개요
일반적으로 개인 컴퓨터나 채점용 컴퓨터에서 1초에 실행할 수 있는 연산량은 1억번이다.
따라서 문제를 풀기 전에 문제의 시간 복잡도를 확인한다면, 얼마나 효율적인 알고리즘을 작성해야하는지 눈치 챌 수 있다.
예를 들어 입력값 N의 최대 범주가 1 <= N <= 10000이고, 주어진 제한 시간이 1초라고 가정해보자.
이중 for문 같은 시간 복잡도가 N^2 인 알고리즘의 연산 횟수는 10000 * 10000 = 1억이기에, 일반적으로 추가적인 연산을 고려한다면 시간 초과의 에러가 날 수 있다고 할 수 있다.
추가적으로 다음과 같은 예시로 생각해보자.
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) * N 이하인 알고리즘을 설계하는게 좋다.
참고)
이것이 취업을 위한 코딩 테스트다. with python
안녕하세요.