시간 복잡도(빅오 표기법)

알고리즘 분석에는 2가지 측면이 있다.

알고리즘의 수행시간 분석을 시간 복잡도

알고리즘이 필요로 하는 기억공간 분석을 공간 복잡도

이 중 알고리즘이 차지하는 공간보다는 수행 시간에 더 관심이 있기 때문에, 알고리즘의 복잡도를 말할 땐 주로 시간 복잡도를 의미한다.

 

시간 복잡도를 표시하는 방법을 빅오 표기법이라고 하는데,

예를 들어 알고리즘이 n에 비례하는 수행시간을 가진다고 말하는 대신에, 알고리즘 A의 시간 복잡도가 O(n)이라고 표기한다.

빅오 표기법은 입력의 개수에 따른 기본 연산의 수행 횟수를 나타낸 것으로, 알고리즘의 대략적인 수행시간을 추정할 수 있다.

최악의 경우(자료 집합 중 수행시간이 가장 오래 걸리는 경우)의 수행시간이 알고리즘의 시간 복잡도 척도로 쓰인다.

빅오 표기법에 의한 알고리즘의 수행 시간을 비교하면 아래와 같다.

 

 

O(1) - 상수 시간

int getFirstElement(int[] arr) {
    return arr[0];  // 배열 크기에 상관없이 한 번만 실행됨
}

 

 

O(log n) - 로그 시간

이진 탐색은 배열이 정렬된 상태에서만 사용할 수 있으며, 매번 배열을 절반으로 나누어 값을 찾는다.

배열 크기가 두 배로 증가해도, 비교 횟수는 한 번씩만 증가하므로 O(log n)

int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid; // 값 찾음
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // 값 없음
}

 

 

 

O(n) - 선형 시간

열을 순차적으로 탐색하는 경우

배열 크기 n에 비례하여 연산 횟수가 증가하므로 O(n)

int sum(int[] arr) {
    int total = 0;
    for (int i = 0; i < arr.length; i++) {
        total += arr[i];  // 배열의 모든 요소를 순차적으로 더함
    }
    return total;
}

 

 

O(n log n) - 로그-선형 시간

병합 정렬, 퀵 정렬, 힙 정렬

배열을 반복적으로 절반으로 나누고, 나누어진 배열을 정렬하고 병합하는 방식

배열을 절반씩 나누어 log n 번의 분할이 이루어지고, n 개의 요소를 병합하므로 O(n log n)

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        mergeSort(arr, left, mid);  // 왼쪽 절반 정렬
        mergeSort(arr, mid + 1, right);  // 오른쪽 절반 정렬
        
        merge(arr, left, mid, right);  // 병합
    }
}

 

 

O(n²) - 이차 시간

버블 정렬, 선택 정렬, 삽입 정렬

이중 반복문을 사용하여 두 요소를 비교하고 교환하는 방식

이중 반복문을 사용하여 배열의 크기 n에 비례하여 연산이 증가하므로 O(n²)

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

 

 

O(2ⁿ) - 지수 시간

피보나치 수열

재귀적으로 두 번씩 호출이 이루어져서 지수적으로 연산 횟수가 증가

n이 커질수록 호출되는 함수의 수가 급격히 증가하므로 O(2ⁿ)

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);  // 재귀 호출
}

 

 

O(n!) - 팩토리얼 시간

순열

모든 순열을 구하는 문제는 가능한 모든 순서를 탐색해야 하므로 O(n!)

void permute(int[] arr, int l, int r) {
    if (l == r) {
        System.out.println(Arrays.toString(arr));
    } else {
        for (int i = l; i <= r; i++) {
            swap(arr, l, i);  // 요소를 교환
            permute(arr, l + 1, r);  // 재귀적으로 순열 생성
            swap(arr, l, i);  // 백트래킹
        }
    }
}

void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 

// 추후 정렬 공부하고 내용 보완