[Algorithm] 시간 복잡도 정리

 

[Algorithm] 시간 복잡도 정리

입력 제한에 따라 어떠한 알고리즘을 사용할지 정할 수 있는데 이는 아래와 같습니다.

1. n <= 20  : 웬만한건 모두 통과
   →  브루트포스 알고리즘
   → O(n!), O(2^n)
2. n <= 100 : 삼중 루프 가능
   → 폴로리드 와샬 알고리즘
   → O(n^3)
3. n <= 1000  : 이중 루프 가능
   → 벨만포트 알고리즘
   → O(n^2)
4. n <= 10000 : 알고리즘을 이용하여 풀어야 함
   → 동적 프로그래밍, 이분탐색, 다익스트라 알고리즘, 유니언 파인드, 세그먼트 트리, 투포인터
   → O(n), O(nlogn)
5. n <= 10^8
   → 유클리드의 호제법
   → O(logn)