시간 복잡도 알고리즘 선택 기준

컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다.

따라서 코딩 테스트의 경우 연산 횟수는 1,000~3,000만 정도로 고려해서 시간 복잡도를 생각하면 된다.

예를 들어 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘은 사용하면 안된다.

 

제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 N의 가용 범위는 아래와 같다.

시간 복잡도	N의 가용 범위
O(N!)	10
O(2ⁿ)	20~25
O(N³)	200~300
O(N²)	3,000 ~ 5,000
O(NlogN)	100만
O(N)	1,000~2,000만
O(logN)	10억

 

시간 복잡도 초과 예제)

제약 조건

• 정수 배열의 길이는 2이상 10⁵입니다.
• 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하입니다.

정수 배열의 길이는 최대 10⁵ 즉, 10만이다. 

따라서 O(N²)은 사용할수가 없다.

 

그럴리는 없지만 제한 시간이 34초 이상이라면 3,000 x 34가 10만을 초과하므로 가능할것이다.