알고리즘 분석

Posted Apr 19, 2025

By Jaebaek Lee

12 min read

알고리즘 분석

Algorithm Efficiency

효율적 알고리즘
1. 이해, 구현, 유지보수가 쉬운 알고리즘
2. 시간과 공간을 최소화하는 알고리즘
알고리즘 효율성 척도
- 경험적 방법
  - 알고리즘을 실제로 구현하여 성능을 측정
- 이론적 방법
  - 입력 크기 ( n )에 대한 알고리즘의 이론적 성능을 예측
  - 기본 연산의 수를 세어 성능을 분석
기본 연산
- 입력 크기 ( n )에 의존하지 않고 항상 일정한 시간에 수행되는 연산
- 예시:
  - 배열의 원소 접근
  - 변수 대입
  - 산술 연산
  - 비교 연산
- 기본 연산의 수를 세어 알고리즘의 성능을 분석
제어문
- 반복문, 조건문 등이 사용될때의 알고리즘의 성능 분석
- 예시:
  - 반복문(for, while): ( n )번 반복하는 경우 ( O(n) )
  - 조건문(if, else): 조건 만족시 시행되는 알고리즘과 그렇지 않은 않을 때 시행되는 알고리즘 중 더 큰 시간복잡도를 가지는 경우를 기준으로 성능 분석
  - switch문: 가장 큰 시간복잡도를 가지는 경우를 기준으로 성능 분석

예시

  
public static int findMax(int[] array) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

기본 연산: 비교 연산(array[i] > max), 대입 연산(max = array[i])
입력 크기 ( n )에 따라 반복문이 ( n-1 )번 실행됨
비교 연산 횟수: ( n-1 )
대입 연산 횟수: (0 \sim (n-1))
총 기본 연산 횟수: ( n - 1 \sim 2n - 2 )

Best, Worst, Average Case

Best Case: 알고리즘이 가장 빠르게 동작하는 경우
Worst Case: 알고리즘이 가장 느리게 동작하는 경우
Average Case: 알고리즘이 평균적으로 동작하는 경우
주의
- Best, Worst, Average Case를 비교할 때는 입력 크기 ( n )에 따라 성능을 비교해야 함
  - 예를 들어, $n = 1$일때 알고리즘이 제일 빠르므로 그 상화잉 Best Case라고 할 수 없음

예시
주어진 값 k를 찾는 알고리즘

  
public static int findk(int[] array, int k) {
    for (int i = 1; i < array.length; i++) {
          if (array[i] == k) {
              return i;
          }
    }
    return max;
}

Best Case: ( O(1) ) (k가 첫 번째 원소일 때)
Worst Case: ( O(n) ) (k가 마지막 원소일 때)
Average Case: ( O(n) ) (k가 중간에 있을 때)

Asymptotic Analysis

Asymptotic Notation: 알고리즘의 성능을 입력 크기 ( n )에 대한 함수로 표현하는 방법
Big O Notation: 알고리즘의 성능을 상한으로 표현
- 정의:
  - 비공식 정의 :
    ( f(n) )이 ( g(n) )보다 느리게 증가할 때, ( f(n) = O(g(n)) )
  - 공식 정의 :
    [ \exists c > 0, n_0 > 0 : f(n) \leq c \cdot g(n), \forall n \geq n_0 \Rightarrow f(n) = O(g(n)) ]
- 예시:
  ( f(n) = 3n^2 + 2n + 1 )
  - ( g(n) = n^2 )
  - ( c = 4, n_0 = 1 )
  - ( f(n) \leq 4n^2 ) (모든 ( n \geq 1 ))
  - 따라서 ( f(n) = O(n^2) )
Big Omega Notation: 알고리즘의 성능을 하한으로 표현
- 정의:
  - 비공식 정의 :
    ( f(n) )이 ( g(n) )보다 빠르게 증가할 때, ( f(n) = \Omega(g(n)) )
  - 공식 정의 :
    [ \exists c > 0, n_0 > 0 : f(n) \geq c \cdot g(n), \forall n \geq n_0 \Rightarrow f(n) = \Omega(g(n)) ]
- 예시:
  ( f(n) = 3n^2 + 2n + 1 )
  - ( g(n) = n^2 )
  - ( c = 1, n_0 = 1 )
  - ( f(n) \geq n^2 ) (모든 ( n \geq 1 ))
  - 따라서 ( f(n) = \Omega(n^2) )
Big Theta Notation: Big Omega와 Big O를 동시에 만족하는 경우
- 정의:
  - 비공식 정의 :
    ( f(n) )이 ( g(n) )과 같은 속도로 증가할 때, ( f(n) = \Theta(g(n)) )
  - 공식 정의 :
    [ \exists c_1, c_2 > 0, n_0 > 0 : c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n), \forall n \geq n_0 \Rightarrow f(n) = \Theta(g(n)) ]
- 예시:
  ( f(n) = 3n^2 + 2n + 1 )
  - ( g(n) = n^2 )
  - ( c_1 = 1, c_2 = 4, n_0 = 1 )
  - ( n^2 \leq f(n) \leq 4n^2 ) (모든 ( n \geq 1 ))
  - 따라서 ( f(n) = \Theta(n^2) )
Simplifying Rules
- 만약 ( f(n) )이 ( O(g(n)) )이고 ( g(n) )이 ( O(h(n)) )이면, ( f(n) )은 ( O(h(n)) )
- 만약 ( f(n) )이 어떤 상수 ( k > 0)에 대해 ( O(kg(n)) )이면, ( f(n) )은 ( O(g(n)) )
- 만약 ( f_1(n) )이 ( O(g_1(n)) )이고 ( f_2(n) )이 ( O(g_2(n)) )이면, ( f_1(n) + f_2(n) )은 ( O(max(g_1(n), g_2(n))) )
- 만약 ( f_1(n) )이 ( \Theta(g_1(n)) )이고 ( f_2(n) )이 ( \Theta(g_2(n)) )이면, ( f_1(n) + f_2(n) )은 ( \Theta(max(g_1(n), g_2(n))) )
- 만약 ( f_1(n) )이 ( O(g_1(n)) )이고 ( f_2(n) )이 ( O(g_2(n)) )이면, ( f_1(n) \cdot f_2(n) )은 ( O(g_1(n) \cdot g_2(n)) )
- 만약 ( f_1(n) )이 ( \Theta(g_1(n)) )이고 ( f_2(n) )이 ( \Theta(g_2(n)) )이면, ( f_1(n) \cdot f_2(n) )은 ( \Theta(g_1(n) \cdot g_2(n)) )

예제

예시 1:
- ( f(n) = 3n^2 + 2n + 1 < 3n^2 + 2n^2 + n^2 = 6n^2 )
- ( c = 6, n_0 = 1 )
- 따라서 ( f(n) = O(n^2) )

예시 2:

  
  sum = 0;
  for (i = 1; i <= n; i++) {
      for (j = 1; j <= n; j++) {
          sum += i * j;
      }
  }

기본 연산: i * j
- 바깥 반복문: ( n )번
- 안쪽 반복문: ( n )번
- 총 기본 연산 횟수: ( n^2 )
따라서 ( f(n) = O(n^2) )

예시 3:
1 2 3 4 5 6 7 8 9 sum = 0; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { sum++; } } for (k = 0; k < n; k++) { sum++; }
- 첫번째 기본 연산: sum++
  - 첫 번째 반복문: ( n )
  - 두 번째 반복문: ( n )
  - 총 기본 연산 횟수: ( n^2 )
- 두번째 기본 연산: ( sum++ )
  - 반복문: ( n )
  - 총 기본 연산 횟수: ( n )
- 총 기본 연산 횟수: ( n^2 + n )
- 따라서 ( f(n) = O(n^2) )

예시 4:

  
  sum1 = 0;
  for (k = 1; k <= n; k *= 2) {
      for (i = 1; i <= n; i++) {
          sum1++;
      }
  }

  sum2 = 0;
  for (i = 1; i <= n; k *= 2) {
      for (j = 1; j <= k; j++) {
          sum2++;
      }
  }

첫번째 기본 연산: sum1++
- 바깥 반복문: ( \log_2 n )
- 안쪽 반복문: ( n )
- 총 기본 연산 횟수: ( n \log_2 n )
두번째 기본 연산: sum2++
- 바깥 반복문: ( log_2 n )
- 안쪽 반복문: ( k = 1, 2, 4, \ldots, n )
- 총 기본 연산 횟수: [ \sum_{k=1}^{\log_2 n} k = 1 + 2 + 4 + \ldots + n = \frac{2^{\log_2 n + 1} - 1}{2 - 1} = n - 1 ]
따라서 ( f(n) = O(n \log_2 n) )

Binary Search

정렬된 배열에서 특정 값 찾기
- naive approach: 첫 번째 원소부터 끝까지 비교($O(n)$)
- binary search: 중간 원소와 비교하여 절반으로 나누기($O(\log n)$)

Binary Search Algorithm

배열을 정렬
시작 인덱스와 끝 인덱스를 설정
중간 인덱스를 계산
중간 원소와 찾고자 하는 값 비교
- 같으면 중간 인덱스 반환
- 작으면 시작 인덱스를 중간 인덱스 + 1로 변경
- 크면 끝 인덱스를 중간 인덱스 - 1로 변경

값을 찾거나 시작 인덱스가 끝 인덱스를 초과할 때까지 반복

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

 while (left <= right) {
     int mid = left + (right - left) / 2;

     if (array[mid] == target) {
         return mid;
     } else if (array[mid] < target) {
         left = mid + 1;
     } else {
         right = mid - 1;
     }
 }
 return -1; // not found
  }

시간 복잡도: ( O(\log n) )
- 분석
  - 각 반복에서 배열의 크기가 절반으로 줄어듦
  - 최악의 경우 ( \log_2 n )번 반복
  - 따라서 시간 복잡도는 ( O(\log n) )

Space/Time Tradeoff

알고리즘의 시간 복잡도가 줄어들면, 반대로 사용되는 메모리 공간이 증가하는 경우가 있음
- 예시:
  - 메모리 공간을 사용하여 중복 계산을 피하는 경우
  - 메모리 공간을 사용하여 알고리즘의 성능을 향상시키는 경우
  - a와 b의 값 교환(공간 최적화)
    - a = a + b
    - b = a - b
    - a = a - b
Disk-based Space/Time Tradeoff
- 디스크 저장공간이 줄어들면, 해당 디스크에 접근하는 프로그램이 빨라지는 경우

해당 포스트는 서울대학교 컴퓨터공학부 강유 교수님의 자료구조 25-1학기 강의를 정리한 내용입니다.

자료구조

This post is licensed under CC BY 4.0 by the author.