[알고리즘] 알고리즘의 효율과 시간 복잡도 (Big-O 표기법)

알고리즘의 효율

• 효율적인 알고리즘의 설계는 프로그램 개발에서 필수적인 요소
• 알고리즘의 성능은 시간적 효율성과 공간적 효율성 관점에서 평가
• 효율성 = 복잡도(complexity) >> 즉, 복잡도가 높을수록 효율성은 저하됨

시간적 효율성과 공간적 효율성

시간적 효율성	공간적 효율성
알고리즘이 실행되는 데 걸리는 시간	알고리즘이 사용하는 메모리(공간)의 양
연산량 대비 얼마나 적은 시간을 필요로 하는가	연산량 대비 얼마나 적은 메모리 공간을 필요로 하는가

시간과 공간의 트레이드 오프

일반적으로 알고리즘은 시간과 공간 중 하나를 희생하여 다른 하나를 최적화하는 방식으로 설계

• 시간적 효율성을 우선시 하는 경우
  • 실행 시간을 줄이기 위해 더 많은 메모리를 사용하는 캐싱이나 해시 테이블을 활용
  • ex) 동적 프로그래밍(DP, Dynamic Programming)
• 공간적 효율성을 우선하는 경우
  • 메모리를 아끼기 위해 시간이 더 걸리는 연산을 반복 수행
  • ex) 재귀 대신 반복문 사용

시간적 효율성의 중요도

현대 소프트웨어와 시스템에서 시간적 효율성은 사용자 경험과 직접적으로 연관

• 실시간 요구
  • 검색 엔진, 게임 서버, 금융 시스템 등은 실시간 데이터 처리가 중요하며, 실시간 데이터 처리에서는 시간적 효율성이 핵심
• 대규모 데이터 처리
  • 데이터 크기가 클수록 시간 복잡도가 낮은 알고리즘의 중요성이 크게 작용
  • ex) 머신 러닝, 대규모 데이터 분석 (빅데이터)

---

시간 복잡도 (Time Complexity)

시간 복잡도의 정의

• 알고리즘이 수행되는 데 걸리는 시간을 입력 크기와의 관계로 표현한 것
• 입력 크기($ n $)가 증가할 때, 알고리즘의 성능을 수학적으로 분석하여 여러 개의 항을 가지는 다항식으로 표현
• 알고리즘의 성능을 수학적으로 분석하는 데 점근적 표기(asymptotic notation)를 사용하며, 입력 크기 $ n $이 무한대로 커질 때의 복잡도를 계수를 제외한 최대 차수 항으로만 표현

시간 복잡도의 표기법

Big-O 표기법 ( $ O $ )

• 정의 : 알고리즘의 최악의 경우 실행 시간의 상한(upper bound)을 나타냄
• 목적 : 입력 크기가 커질수록 알고리즘이 얼마나 느려질 수 있는지를 평가
• 특징
  • 알고리즘이 절대로 그 이상 느려지지 않는다는 것을 보장
  • "이 정도 시간 이내에는 끝난다"라는 약속을 표현
• 수학적 정의
  • 알고리즘의 실행 시간이 $T(n)$이라고 할 때,
    $ T(n) \in O( f(n) ) $은 $$ T(n) \le c \cdot f(n), \;\;\;\; for \; all \; n \ge n_0 $$ 를 만족하는 $ c > 0 $와 $ n_0 $가 존재할 때 성립
• ex) $ T(n) = 3n^2 + 2n + 1 $이라면, Big-O 표기법으로 $ O(n^2) $
  (최악의 경우, $ n^2 $ 이상의 성능 저하가 발생하지 않음을 보장)

Big-Theta 표기법 ( $ \Theta $ )

• 정의 : 알고리즘의 실행 시간이 입력 크기 $ n $에 대해 정확하게 어느 정도 비례하는지를 나타냄
• 목적 : 알고리즘의 실행 시간이 특정 함수에 정확히 근접함을 분석
• 특정
  • 알고리즘의 상한(upper bound)과 하한(lower bound)을 동시에 나타냄
  • "이 정도 시간에 정확히 비례한다"라는 표현
• 수학적 정의
  • 알고리즘의 실행 시간이 $ T(n) $이라고 할 때,
    $ T(n) \in \Theta ( f(n) ) $은 $$ c_1 \cdot f(n) \le T(n) \le c_2 \cdot f(n), \;\;\;\; for \; all \; n \ge n_0 $$를 만족하는 $ c_1,\; c_2 > 0 $와 $ n_0 $가 존재할 떄 성립
• ex) $ T(n) = 3n^2 + 2n + 1 $이라면, Big-Theta 표기법으로 $ \Theta (n^2) $
  ($ n $이 충분히 커질수록 $ n^2 $에 정확하게 비례)

Big-Omega 표기법 ( $ \Omega $ )

• 정의 : 알고리즘의 실행 시간이 최선인 경우 실행 속도의 하한(얼마나 빨리 실행될 수 있는지)을 나타냄
• 목적 : 입력 크기가 커질수록 알고리즘이 최소한 어느 정도의 성능을 낼 수 있는지를 보장
• 특징
  • 알고리즘이 절대로 이 이하로는 빨라지지 않는 하한(lower bound)을 표현
  • "이 정도 시간 이상은 반드시 걸린다"라는 약속을 표현
• 수학적 정의
  • 알고리즘의 실행 시간이 $ T(n) $이라고 할 때,
    $ T(n) \in \Omega ( f(n) ) $은 $$ T(n) \ge c \cdot f(n), \;\;\;\; for \; all \; n \ge n_0 $$를 만족하는 $ c_1, c_2 > 0 $와 $ n_0 $가 존재할 때 성립
• ex) $ T(n) = 3n^2 + 2n + 1 $이라면, Big-Omega 표기법으로 $ \Omega (n^2) $
  (최선의 경우에도 $ n^2 $ 이상의 성능이 요구됨)

Big-O, Big-Theta, Big-Omega의 관계

표기법	의미	초점	관계
Big-O ( $ O $ )	최악의 경우 (상한)	성능의 한계	알고리즘의 느려질 수 있는 최대 속도를 나타냄
Big-Theta ( $ \Theta $ )	평균적인 경우 (평균)	정확도	가장 정확한 표현으로, 알고리즘의 동작 시간에 대해 상한과 하한을 동시에 정의
Big-Omega ( $ \Omega $ )	최선의 경우 (하한)	최소 보장	알고리즘이 가장 빨리 수행될 경우의 시간을 나타냄

• 관계 : $ \Omega ( f(n) ) \le \Theta ( (f(n) ) \le O( f(n) ) $ (Big-Theta는 Big-O와 Big-Omega의 교집합)

알고리즘의 최악의 성능을 평가하는 것이 현실적이기 때문에 Big-O 표기법을 일반적으로 가장 많이 사용

---

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

Big-O 표기법의 기본 개념

• Big-O는 최악의 시간 복잡도를 나타내며, 알고리즘이 실행되는 시간이 입력 크기 $ n $에 대해 어떻게 증가하는지를 설명
• 알고리즘이 최악의 경우, 얼마나 효율적인지 예측하는 데 유용

입력 크기 : 알고리즘이 처리해야 할 데이터의 양
최악의 경우 : 알고리즘이 최대로 걸리는 시간 (가장 비효율적인 경우)

Big-O 표기법의 특징

• 상한선 (upper bound)
  • 알고리즘이 최악의 경우에 절대로 초과하지 않는 시간을 나타냄
  • 알고리즘의 실행 시간이 주어진 시간 복잡도보다 더 길어질 수 없음
• 단순화된 표현
  • 알고리즘 성능을 설명할 때, 불필요한 상수나 낮은 차수 항들을 무시
  • ex) 시간 함수가 $ T(n) = 3n^2 + 2n + 5 $ 이라면, $ O(n^2) $으로 표현

자주 사용되는 Big-O 표기

$ O(1) $ : 상수 시간 복잡도

• 의미 : 알고리즘의 실행 시간이 입력 크기와 무관하게 일정
• 예시 : 배열의 첫 번쨰 원소를 접근하는 경우

int firstElement(int arr[]) {
    return arr[0];  // O(1)
}

$ O( \log n) $ : 로그 시간 복잡도

• 의미 : 알고리즘의 실행 시간이 입력 크기 $ n $ 에 대해 로그 함수의 형태로 증가
• 예시 : 이진 탐색 (binary search)

int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) high = mid - 1;
        else low = mid + 1;
    }
    return -1;  // O(log n)
}

$ O(n) $ : 선형 시간 복잡도

• 의미 : 알고리즘의 실행 시간이 입력 크기 $ n $ 에 비례
• 예시 : 배열을 순차적으로 탐색하는 경우

int findMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;  // O(n)
}

$ O(n \log n) $ : 선형 로그 시간 복잡도

• 의미 : 알고리즘의 실행 시간이 $ n $ 과 $ \log n $ 의 곱에 비례
• 예시 : 병합 정렬 (merge sort), 퀵 정렬 (quick sort)

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}  // O(n log n)

$ O(n^2) $ : 이차 시간 복잡도 (제곱 시간 복잡도)

• 의미 : 알고리즘의 실행 시간이 입력 크기 $ n $ 의 제곱에 비례
• 예시 : 이중 for문을 사용한 경우

void printPairs(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << arr[i] << ", " << arr[j] << endl;
        }
    }
}  // O(n^2)