시간 복잡도

시간 복잡도란?

시간 복잡도(Time Complexity)는 알고리즘이 입력 크기(데이터 개수, nnn)에 따라 실행되는 데 걸리는 시간을 표현하는 척도. 알고리즘의 효율성을 비교할 수 있다. 시간 복잡도는 보통 빅오 표기법(Big-O Notation - https://gangdonggil.tistory.com/15)을 사용하여 최악의 경우에 걸리는 시간을 나타낸다.

 

주요 시간 복잡도 비교

시간 복잡도	입력 크기 (n=10)	입력 크기 (n=1,000)	설명
O(1)	1회 실행	1회 실행	입력 크기에 상관없이 일정
O(log ⁡n)	4회 실행	10회 실행	입력 크기 증가에도 느리게 증가
O(n)	10회 실행	1,000회 실행	입력 크기만큼 실행
O(n^2)	100회 실행	1,000,000회 실행	입력 크기 제곱만큼 실행

 

결론

• 시간 복잡도는 알고리즘의 효율성을 비교하는 척도로 매우 중요.
• O(1), O(log ⁡n), O(n), O(n^2) 등 주요 시간 복잡도를 이해하면 효율적인 코드를 작성할 수 있다.
• 실제로 문제를 풀 때, 가능한 가장 낮은 시간 복잡도를 가진 알고리즘을 선택하는 것이 좋다.