NOTE 시간 복잡도
시간 복잡도는 쉽게 말해 삽입, 삭제와 같은 알고리즘 연산을 수행하는 데 걸리는 시간을 의미합니다. 보통 ‘최악의 경우 얼마의 시간이 걸리는지’를 나타내는 빅오(Big-O) 표기법을 많이 사용합니다. 다음은 빅오 표기법으로 작성한 시간 복잡도의 예입니다.
• O(1): 상수 시간 복잡도입니다. 입력되는 요소 수에 상관없이 항상 동일한 시간이 걸립니다.
• O(log n): 로그 시간 복잡도입니다. 로그는 지수적으로 증가하는 값으로, 입력되는 요소 수가 많아져도 비교적 시간 상승폭이 완만합니다.
• O(n): 선형 시간 복잡도입니다. 입력되는 요소 수에 비례해 시간이 걸립니다.
• O(n2): 제곱 시간 복잡도입니다. 입력되는 요소 수의 제곱에 비례해 시간이 걸립니다.
다음 그림은 알고리즘에 입력되는 요소 수에 따른 알고리즘 수행 시간, 즉 시간 복잡도를 비교한 그래프입니다. 보통 O(n2) 이상부터 알고리즘의 성능이 좋지 않다고 봅니다. 그러나 성능 평가는 상대적인 것이라 경우에 따라 좋고 나쁨이 달라질 수 있습니다.
그림 2-30 입력되는 요소 수에 따른 알고리즘 수행 시간