알고리즘 시간관련 - 시간 제한, 시간 복잡도

우리는 문제를 풀면서 알고리즘 문제가 어떤 유형의 문제인지 판단해야한다.

그 중 한가지 팁인데 시간제한을 보는것이다.

 

인풋에 대한 적절한 시간 복잡도

• N의 범위가 500: 시간 복잡도 O(N^3) 이하
• N의 범위가 2,000: 시간 복잡도 O(N^2) 이하
• N의 범위가 100,000: 시간 복잡도 O(N log N) 이하
• N의 범위가 10,000,000: 시간 복잡도 O(N) 이하
• N의 범위가 10,000,000,000: 시간 복잡도 O(log N) 이하

 

N의 범위가 500 : 시간 복잡도: O(N^3) 이하

• 500^3 = 125,000,000 < 5 * 10^7 (0.5초 안에 실행 가능)
• 예시 알고리즘: 플로이드-워셜, 3중 for 문을 사용하는 알고리즘

N의 범위가 2,000 : 시간 복잡도: O(N^2) 이하

• 2,000^2 = 4,000,000 < 5 * 10^7 (0.5초 안에 실행 가능)
• 예시 알고리즘: 행렬 곱셈, 다익스트라 (인접 행렬로 표현 시)

N의 범위가 100,000 : 시간 복잡도: O(N log N) 이하

• 100,000 * log(100,000) ≈ 100,000 * 17 ≈ 1,700,000 < 5 * 10^7 (0.5초 안에 실행 가능)
• 예시 알고리즘: 병합 정렬, 퀵 정렬, 힙 정렬

N의 범위가 10,000,000 : 시간 복잡도: O(N) 이하

• 10,000,000 < 5 * 10^7 (0.5초 안에 실행 가능)
• 예시 알고리즘: 선형 시간 정렬 (계수 정렬, 기수 정렬), 단순 탐색

N의 범위가 10,000,000,000 : 시간 복잡도: O(log N) 이하

• log(10,000,000,000) ≈ 33 < 5 * 10^7 (0.5초 안에 실행 가능)
• 예시 알고리즘: 이진 탐색, 균형 잡힌 이진 검색 트리 연산