시간복잡도

왕·2023년 5월 17일

시간복잡도

시간 복잡도(Time Complexity)는 알고리즘의 실행 시간이 입력 크기에 대해 어떻게 증가하는지를 설명하는 개념이다. 일반적으로 더 빠른 알고리즘은 입력 크기가 증가함에 따라 더 적은 시간이 소요된다.

시간 복잡도는 빅오 표기법(Big O Notation)을 사용하여 표현된다. 몇 가지 흔히 사용되는 시간 복잡도의 예시는 다음과 같다.

O(1) - 상수 시간(Constant time)

void printFirstElement(int[] array) {
    System.out.println(array[0]);
}

입력 크기에 관계없이 일정한 실행 시간을 가지는 경우이다. 예를 들어, 배열에서 특정 인덱스의 요소를 찾는 경우이다.

O(log n) - 로그 시간(Logarithmic time)

void binarySearch(int[] sortedArray, int target) {
    int left = 0;
    int right = sortedArray.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (sortedArray[mid] == target) {
            // 원하는 값 찾음
            return;
        } else if (sortedArray[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // 원하는 값이 없음
    return;
}

입력 크기의 로그에 비례하는 실행 시간을 가지는 경우이다. 이진 탐색과 같이 입력을 절반씩 분할하여 탐색하는 알고리즘이 이에 해당한다.

O(n) - 선형 시간(Linear time)

void linearSearch(int[] array, int target) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            // 원하는 값 찾음
            return;
        }
    }

    // 원하는 값이 없음
    return;
}

입력 크기에 비례하여 선형적으로 실행 시간이 증가하는 경우이다. 배열의 모든 요소를 한 번씩 확인하는 경우이다.

O(n^2) - 이차 시간(Quadratic time)

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

입력 크기의 제곱에 비례하는 실행 시간을 가지는 경우이다. 이중 반복문을 사용하여 모든 요소 쌍을 확인하는 경우이다.

O(2^n) - 지수 시간(Exponential time)

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

입력 크기에 대해 지수 함수에 비례하는 실행 시간을 가지는 경우이다. 조합, 순열과 같은 모든 가능한 경우의 수를 확인하는 경우이다.
재귀적인 구조나 모든 부분집합을 생성하는 경우에 해당한다.

시간복잡도 계산

void printPairs(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            System.out.println(array[i] + ", " + array[j]);
        }
    }
}

위의 코드는 주어진 배열의 각 요소들을 조합하여 쌍을 출력하는 함수이다. 이 코드의 시간 복잡도를 계산해보자.

외부 루프는 배열의 길이에 비례하는 O(n)의 시간이 소요된다. 내부 루프는 외부 루프의 반복 횟수에 따라 달라지며, 첫 번째 반복에서 (n-1)번, 두 번째 반복에서 (n-2)번, ..., 마지막 반복에서 1번의 연산이 수행된다. 이러한 내부 루프의 연산은 등차수열의 합과 관련이 있으며, 최종적으로 (n-1) + (n-2) + ... + 1 = n(n-1)/2 번의 연산이 수행된다.
따라서, 위의 예시 코드의 시간 복잡도는 O(n^2) 이다.

시간 복잡도를 고려할 때는 알고리즘의 효율성을 평가하고, 입력 크기에 따른 성능 예측과 알고리즘 선택에 도움을 준다. 더 작은 시간 복잡도를 가지는 알고리즘을 선택하면 보다 효율적인 프로그램을 개발할 수 있다.

자료형별 시간복잡도

배열(Array)

접근 (Access): O(1)
검색 (Search): O(n) - 선형 검색(linear search)을 수행해야 함
삽입 (Insertion): O(n) - 배열의 중간이나 처음에 원소를 삽입할 경우, 삽입 위치 이후의 원소들을 한 칸씩 뒤로 이동해야 함
삭제 (Deletion): O(n) - 배열에서 원소를 삭제할 경우, 삭제 위치 이후의 원소들을 한 칸씩 앞으로 이동해야 함

연결 리스트 (Linked List)

특정 위치에 직접 접근하기 위해서는 처음부터 해당 위치까지 순회해야 하므로, 접근 및 검색은 최악의 경우 O(n)입니다. 추가 및 삭제는 해당 위치까지 순회한 뒤에 삽입 또는 삭제를 수행하므로, 일반적으로 O(1)이다.

이진 검색 트리 (Binary Search Tree)

트리의 균형 상태에 따라 접근, 검색, 추가, 삭제 모두 평균적으로 O(log n)이다. 하지만 트리가 한쪽으로 치우쳐진 경우 최악의 경우 O(n)의 시간이 소요될 수 있다.

우선순위 큐 (Priority Queue)

일반적으로 우선순위 큐는 힙(heap) 자료구조를 기반으로 구현된다. 요소의 추가는 O(log n), 삭제는 O(log n), 최대 또는 최소값 조회는 O(1)이다.

해시맵(HashMap)

해시 함수를 사용하여 키-값 쌍을 저장
접근 (Access): O(1) - 키(key)를 통해 값(value)에 직접 접근 가능
검색 (Search): O(1) - 해시맵은 내부적으로 해시 함수를 사용하여 키를 해시값으로 변환하고, 이를 통해 값을 검색하기 때문에 상수 시간에 접근 가능
삽입 (Insertion): O(1) - 해시맵은 내부적으로 해시 함수를 사용하여 키를 해시값으로 변환하고, 이를 통해 값을 삽입하기 때문에 상수 시간에 삽입 가능
삭제 (Deletion): O(1) - 해시맵은 내부적으로 해시 함수를 사용하여 키를 해시값으로 변환하고, 이를 통해 값을 삭제하기 때문에 상수 시간에 삭제 가능