시간복잡도

개념

시간 복잡도는 알고리즘의 효율성을 측정하는 데 사용되는 중요한 개념입니다. 이는 알고리즘이 실행되는 데 걸리는 시간과 입력 데이터의 크기 사이의 관계를 나타냅니다. 시간 복잡도를 분석함으로써 우리는 알고리즘이 입력 크기가 커짐에 따라 얼마나 빠르게 실행 시간이 증가하는지 예측할 수 있습니다.

시간 복잡도를 설명할 때 주로 사용되는 표기법은 빅오 표기법(Big-O notation)입니다. 빅오 표기법은 최악의 경우를 나타내며, 알고리즘의 성능을 표현하는 데 사용됩니다.

주요 시간 복잡도 종류

하나. O(1) - 상수 시간 복잡도 (Constant Time)

• 입력 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘.
• 예: 배열의 특정 인덱스에 접근하기.

둘. O(log n) - 로그 시간 복잡도 (Logarithmic Time)

• 입력 크기가 커질수록 실행 시간이 로그함수 형태로 증가하는 알고리즘.
• 예: 이진 탐색(Binary Search).

셋. O(n) - 선형 시간 복잡도 (Linear Time)

• 입력 크기에 비례하여 실행 시간이 증가하는 알고리즘.
• 예: 배열의 모든 원소를 한 번씩 탐색하는 알고리즘.

넷. O(n log n) - 선형 로그 시간 복잡도 (Linearithmic Time)

• 선형 시간과 로그 시간의 복합 형태.
• 예: 효율적인 정렬 알고리즘 (합병 정렬, 퀵 정렬).

다섯. O(n^2) - 이차 시간 복잡도 (Quadratic Time)

• 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘.
• 예: 버블 정렬, 삽입 정렬.

여섯. O(2^n) - 지수 시간 복잡도 (Exponential Time)

• 입력 크기가 증가할 때 실행 시간이 지수 함수 형태로 증가하는 알고리즘.
• 예: 피보나치 수열의 비효율적인 재귀적 구현.

일곱. O(n!) - 팩토리얼 시간 복잡도 (Factorial Time)

• 입력 크기의 팩토리얼에 비례하여 실행 시간이 증가하는 알고리즘.
  예: 순열 생성 알고리즘.

시간 복잡도 분석의 중요성

• 성능 예측: 입력 데이터가 매우 큰 경우에도 알고리즘이 효율적으로 작동할 수 있는지 예측할 수 있습니다.
• 자원 절약: 효율적인 알고리즘을 사용함으로써 시스템 자원을 절약하고, 성능을 최적화할 수 있습니다.
• 비교 기준: 여러 알고리즘을 비교할 때 시간 복잡도는 중요한 기준이 됩니다.

예제

각 시간 복잡도를 설명하기 위해 Java 코드 예제를 포함하여 설명하겠습니다.

1. O(1) - 상수 시간 복잡도 (Constant Time)

입력 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘입니다.

public int getFirstElement(int[] arr) {
    return arr[0];  // 항상 일정한 시간에 실행
}

2. O(log n) - 로그 시간 복잡도 (Logarithmic Time)

입력 크기가 커질수록 실행 시간이 로그함수 형태로 증가하는 알고리즘입니다.

public 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;  // 찾지 못했을 때
}

3. O(n) - 선형 시간 복잡도 (Linear Time)

입력 크기에 비례하여 실행 시간이 증가하는 알고리즘입니다.

public int findMax(int[] arr) {
    int max = arr[0];

    for (int num : arr) {
        if (num > max) {
            max = num;
        }
    }

    return max;
}

4. O(n log n) - 선형 로그 시간 복잡도 (Linearithmic Time)

선형 시간과 로그 시간의 복합 형태입니다.

import java.util.Arrays;

public void sortArray(int[] arr) {
    Arrays.sort(arr);  // 정렬 알고리즘 (예: 합병 정렬, 퀵 정렬)이 O(n log n)의 시간 복잡도를 가짐
}

5. O(n^2) - 이차 시간 복잡도 (Quadratic Time)

입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘입니다.

public 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 arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

6. O(2^n) - 지수 시간 복잡도 (Exponential Time)

입력 크기가 증가할 때 실행 시간이 지수 함수 형태로 증가하는 알고리즘입니다.

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

7. O(n!) - 팩토리얼 시간 복잡도 (Factorial Time)

입력 크기의 팩토리얼에 비례하여 실행 시간이 증가하는 알고리즘입니다.

public void generatePermutations(int[] arr, int n) {
    if (n == 1) {
        System.out.println(Arrays.toString(arr));
        return;
    }

    for (int i = 0; i < n; i++) {
        generatePermutations(arr, n - 1);

        if (n % 2 == 0) {
            int temp = arr[i];
            arr[i] = arr[n - 1];
            arr[n - 1] = temp;
        } else {
            int temp = arr[0];
            arr[0] = arr[n - 1];
            arr[n - 1] = temp;
        }
    }
}

각 시간 복잡도에 대한 예제는 다양한 입력 크기에 대한 알고리즘의 성능을 이해하는 데 도움이 됩니다. 이 예제들을 통해 알고리즘의 효율성을 평가하고 적절한 알고리즘을 선택하는 능력을 기를 수 있습니다.