시간복잡도

1. 개요

알고리즘의 시간복잡도에 대해 알아보자.

2. 정의

시간 복잡도 : 문제를 해결하기 위한 연산 횟수, 일반적으로 1억 번의 연산을 1초로 간주

3. 유형

1. 빅-오메가 Ω(n) : 최선일 때 (Best case)
2. 빅-세타 θ(n) : 보통일 때 (Average case)
3. 빅-오 O(n) : 최악일 때 (Worst case) -> 코딩테스트에서는 빅-오를 염두하고 임한다.
   -> 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야 하기 때문이다.

문제의 시간복잡도를 충족하며 해결하기 위해서는

1. 알맞은 알고리즘을 사용하고

2. 비효율적인 로직 찾아서 효율적으로 바꾼다