시간복잡도

시간복잡도 (Time Complexity)

알고리즘이나 프로그램이 문제를 해결하는 데 필요한 연산 횟수를 나타내는 척도. 입력 크기에 따라 실행 시간이 어떻게 증가하는지를 표현합니다.

•

Big O 표기법 (최악의 경우)

•

입력 크기 (n)

•

기본 연산의 횟수

가장 내부에 있는 기본 연산 파악

반복문이나 재귀의 실행 횟수 계산

전체 수행 시간에 가장 큰 영향을 미치는 항 선택

계수와 낮은 차수의 항 제거

일반적으로 알고리즘의 시간복잡도를 표현할 때는 최악의 경우(Worst Case)를 기준으로 합니다.

•

알고리즘의 성능 보장: 최악의 경우를 알면 그보다 나쁜 성능이 나올 수 없음을 보장할 수 있습니다.

•

안정성 예측: 시스템 설계 시 필요한 자원을 정확하게 예측할 수 있습니다.

•

신뢰성: 사용자에게 최소한의 성능을 보장할 수 있습니다.

하지만 경우에 따라 평균 시간복잡도(Average Case)도 중요할 수 있습니다:

•

실제 사용 환경: 대부분의 경우 평균적인 성능으로 작동하기 때문입니다.

•

퀵정렬의 예: 최악의 경우 O(n²)이지만, 평균적으로 O(nlogn)으로 매우 효율적입니다.