알고리즘 별 시간 복잡도

😎 시간 복잡도

코테 문제를 풀 때 데이터의 크기와 개수를 통해 문제가 요구하는 시간 복잡도를 예측해서 풀어야 한다.

시간 제한 : 5초
첫째 줄에 수열의 길이 n이 주어진다. n은 5000이하 자연수

• 이런 식으로 문제가 요구하는 시간 복잡도가 존재한다.

😓 상황에 따라 문제가 요구하는 시간 복잡도를 간단히 정리

Big-O 계산을 통해서...

1억 (100,000,000 = 10^8 ) → 1초
10억 = 1,000,000,000 = 109 (콤마(,)가 3개 있는 수치)

알고리즘 별 시간 복잡도

• 다익스트라 : O(ElogV)
• 위상정렬 : O(V+E)
• 플로이드-워셜 : O(V^3)
• 백트랙킹 : 보통 지수 꼴 O(2^n)
• DFS : O(N^2)
• BFS : O(N^2)

대충 이렇게 생각하고 어떤 알고리즘일지 추측하면서 진행하면 돼.