24.12.23 TIL 시간복잡도

신성훈·2024년 12월 23일

시간복잡도

TIL

목록 보기

105/162

1. 시간복잡도(Time Complexity)란?

시간복잡도는 알고리즘이 실행되는 데 걸리는 시간을 수학적으로 표현한 것입니다.
특히, 입력 크기 ( n )에 따라 알고리즘의 실행 시간이 어떻게 변하는지 분석합니다.

2. 왜 중요한가?

성능 비교: 여러 알고리즘 중 더 효율적인 것을 선택할 수 있습니다.
확장성 평가: 입력 크기가 커질 때 실행 시간이 어떻게 변할지 예측할 수 있습니다.
최적화: 병목 현상을 줄이고 리소스를 효율적으로 활용하는 데 도움을 줍니다.

3. 시간복잡도의 Big-O 표기법

Big-O 표기법은 입력 크기에 따른 실행 시간의 최악의 증가율을 나타냅니다.
주요 시간복잡도와 예시는 다음과 같습니다:

주요 시간복잡도

( O(1) ): 상수 시간
- 입력 크기에 상관없이 일정한 시간이 걸림
- 예: 배열의 첫 번째 요소를 접근
```
int getFirstElement(int[] arr) {
    return arr[0]; // O(1)
}
```
( O(\log n) ): 로그 시간
- 입력 크기가 커질수록 실행 시간은 느리게 증가
- 예: 이진 탐색
```
int binarySearch(int[] arr, int target) {
    // 이진 탐색 수행
}
```

( O(n) ): 선형 시간

입력 크기와 실행 시간이 비례
예: 배열의 모든 요소 합 계산

int sumArray(int[] arr) {
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i]; // O(n)
    }
    return sum;
}

( O(n \log n) ): 선형 로그 시간
- 효율적인 정렬 알고리즘
- 예: 병합 정렬, 퀵 정렬

( O(n^2) ): 제곱 시간

중첩 반복문이 있을 때
예: 버블 정렬

void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
            }
        }
    }
}

( O(2^n) ): 지수 시간
- 입력 크기 증가에 따라 실행 시간이 급격히 증가
- 예: 피보나치 수열 계산 (재귀)

4. 시간복잡도 분석 방법

1) 반복문

단일 반복문: ( O(n) )
중첩 반복문: ( O(n^2) )

2) 재귀

재귀 호출 횟수에 따라 증가율 분석
예: ( T(n) = T(n-1) + O(1) ) → ( O(n) )

5. 시간복잡도 비교

복잡도	증가율	예시 알고리즘
( O(1) )	일정	배열 요소 접근
( O(\log n) )	느리게 증가	이진 탐색
( O(n) )	선형 증가	단일 반복문
( O(n^2) )	기하급수적으로 증가	중첩 반복문, 버블 정렬
( O(2^n) )	급격히 증가	피보나치 (재귀)