알고리즘의 효율성을 판단하는 객관적 기준인 시간 복잡도(Time Complexity)에 대해 정리했다.
이는 입력 데이터 크기 증가에 따른 성능 변화를 예측하는 도구이다.
시간 복잡도 유형 분석 (Java)
데이터 크기(N)에 따른 연산 횟수 변화를 통해 복잡도를 파악할 수 있다.
// 1. O(1) - 상수 시간
// 데이터 크기와 무관하게 일정한 연산 횟수를 유지한다.
int getFirst(int[] arr) { return arr[0]; }
// 2. O(N) - 선형 시간
// 데이터 양에 비례하여 연산 횟수가 증가한다.
for (int i : arr) { System.out.println(i); }
// 3. O(N^2) - 2차 시간
// 중첩 반복문 사용 시 발생하며, 데이터 증가에 따라 연산량이 급격히 증가한다.
for (int i : arr) {
for (int j : arr) { /* 중첩 로직 */ }
}
// 4. O(log N) - 로그 시간
// 연산마다 처리 범위가 절반으로 감소한다. (예: 이진 탐색)
while (n > 1) { n /= 2; count++; }
설계 지침
데이터 규모가 커질수록 복잡도 간의 성능 차이는 심화된다.
대용량 데이터 처리 시 중첩 반복문을 억제하고 O(log N) 또는 O(N log N) 복잡도를 가진 알고리즘을 선택해야 한다.
성능 최적화의 기반
시간 복잡도 이해를 통해 코드의 실제 동작 성능을 예측할 수 있다.
기능 구현 단계에서 데이터 증가에 따른 확장성을 고려하는 습관이 중요하다.
시간 복잡도는 효율적인 소프트웨어 설계를 위한 필수적인 지표인 것 같다.
