Skip to content

Latest commit

 

History

History
960 lines (642 loc) · 48.7 KB

File metadata and controls

960 lines (642 loc) · 48.7 KB

2주차 이론 — 알고리즘 설계와 복잡도 분석

레포지토리 안내 | English | 한국어

최종 수정일: 2026-11-19

Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein, Ch 2, 3, 4

학습 목표:

  1. 알고리즘의 형식적 속성을 서술하고 유클리드 GCD 알고리즘을 추적할 수 있다
  2. 반복 코드에서 기본 연산 횟수를 세고 그 결과를 T(n)으로 표현할 수 있다
  3. 최선, 최악, 평균 경우 분석을 구별할 수 있다
  4. 정확한 연산 횟수 대신 점근적 표기법을 선호하는 이유를 설명하고, Big-O, Big-Omega, Big-Theta 표기법을 정의하여 공식 정의로 소속을 증명할 수 있다
  5. 반복 대입법과 추측 후 검증법을 사용하여 간단한 점화식을 풀 수 있다
  6. 마스터 정리를 적용하여 분할 정복 점화식의 시간 복잡도를 결정할 수 있다

목차



1. 알고리즘 기초

1.1 알고리즘의 개념

  • 알고리즘은 문제를 해결하기 위한 단계별 절차 또는 방법이다.
  • 이 과목에서 다루는 문제는 컴퓨터를 사용하여 해결한다.
  • 알고리즘은 입력을 받아 출력(해답)을 생성한다.
flowchart LR
    I["입력"] --> A["알고리즘"]
    A --> O["출력"]
Loading

그림 1. 입력을 받아 출력을 생성하는 알고리즘

1.2 알고리즘의 속성

속성 설명
정확성(Correctness) 모든 유효한 입력에 대해 올바른 출력을 생성해야 한다 (같은 입력 → 같은 출력)
실행 가능성(Executability) 각 단계가 컴퓨터에서 실행 가능해야 한다
유한성(Finiteness) 유한한 시간 내에 종료해야 한다
효율성(Efficiency) 시간과 공간 면에서 효율적일수록 가치 있다

표 1. 알고리즘의 네 가지 속성

핵심: 특히 유한성은 중요하다. 무한 루프에 빠지는 프로그램은 알고리즘이 아니다. 예를 들어 while True: pass는 알고리즘이 아니다. 반면 유클리드 GCD는 b가 매번 작아지므로 반드시 0에 도달하여 종료한다.

1.3 유클리드 GCD 알고리즘

알려진 가장 오래된 알고리즘 중 하나로, 기원전 300년경에 기술되었다.

  • 최대공약수(GCD) 는 두 자연수를 모두 나누는 가장 큰 수이다.
  • 핵심 통찰은 GCD(A, B) = GCD(B, A mod B)이다.

수학적 근거:

$A > B$이고, $A = a \cdot G$, $B = b \cdot G$ ($G$ = GCD)일 때:

여기서 $a = A/G$, $b = B/G$는 정수이다($G$가 $A$와 $B$를 모두 나누므로). $a$와 $b$는 서로소(coprime)이다(이들의 GCD는 1).

$$A \mod B = (a \mod b) \cdot G$$

이를 반복 적용하면 $B$가 $0$으로 줄어들고, 그 시점의 $A$가 GCD이다.

증명: $A = B \cdot q + r$ (q는 몫, r은 나머지)이므로 $a \cdot G = b \cdot G \cdot q + r$이다. 따라서 $r = (a - bq) \cdot G = (a \bmod b) \cdot G$이다. 나머지에도 G가 인수로 남아 있으므로 GCD가 보존된다.

의사코드:

Euclid(a, b)
  입력:  정수 a, b  (a >= b >= 0)
  출력:  GCD(a, b)

  if b == 0
      return a
  return Euclid(b, a mod b)

추적: GCD(24, 14)

호출 a b a mod b
1 24 14 10
2 14 10 4
3 10 4 2
4 4 2 0
5 2 0 (2 반환)

표 2. GCD(24, 14)의 호출별 추적

반복(Iterative) 버전:

def gcd_iter(a, b):
    while b != 0:
        a, b = b, a % b
    return a

재귀(Recursive) 버전:

def gcd_rec(a, b):
    if b == 0:
        return a
    return gcd_rec(b, a % b)

두 버전 모두 동일한 결과를 생성한다. 재귀는 호출 스택(call stack) 을 사용하며, 각 호출이 새 프레임을 push한다. 반복은 스택 오버헤드를 회피한다.

[자료구조] 재귀(recursion) 는 함수가 자기 자신을 호출하는 것으로, 모든 재귀 함수는 재귀를 멈추는 기저 사례(base case) 와 문제를 더 작은 크기로 줄여 자기 자신을 호출하는 재귀 단계(recursive step) 로 구성된다. 위 GCD 함수에서는 b == 0이 기저 사례이고 gcd_rec(b, a % b)가 재귀 단계이며, 호출할 때마다 두 번째 인자가 작아져 반드시 기저 사례에 도달하므로 재귀가 끝난다.

재귀 호출 스택 추적:

gcd_rec(24, 14)
  └─► gcd_rec(14, 10)
        └─► gcd_rec(10, 4)
              └─► gcd_rec(4, 2)
                    └─► gcd_rec(2, 0) → returns 2
                  returns 2
            returns 2
      returns 2
returns 2

그림 2. gcd_rec(24, 14)의 재귀 호출과 반환

각 재귀 호출은 스택에 프레임을 push한다. b == 0이 되면 값이 다시 pop되어 올라온다.

[자료구조] 스택은 후입선출(LIFO: Last In, First Out) 자료구조이다. 프로그램의 함수 호출도 스택 구조로 관리되며, 함수가 호출되면 push되고 반환되면 pop된다. 재귀가 너무 깊으면 스택 오버플로(Stack Overflow) 가 발생할 수 있다. Python의 기본 재귀 깊이 제한은 1000이다.

1.4 알고리즘의 표현

알고리즘은 단계별 절차이며, 요리 레시피와 유사하다. 일반적인 표현 방법은 세 가지이다.

방법 설명
자연어 각 단계를 말로 풀어서 설명
의사코드(Pseudocode) 프로그래밍 언어와 유사한 구조화된 표기법 (가장 일반적)
순서도(Flowchart) 도형과 화살표로 된 시각적 다이어그램

표 3. 알고리즘의 세 가지 표현 방법

예시: 최댓값 찾기

문제: $n$장의 숫자 카드에서 가장 큰 수를 찾아라.

그림 3. 손에 든 카드를 비교하며 정리하는 모습

그림 3. 손에 든 카드를 비교하며 정리하는 모습

자연어:

  1. 첫 번째 카드의 숫자를 읽고 기억한다.
  2. 다음 카드를 읽어 기억한 숫자와 비교한다.
  3. 더 큰 수를 기억에 유지한다.
  4. 카드가 남아 있으면 2단계로 간다.
  5. 기억하고 있는 숫자가 최댓값이다.

의사코드:

FindMax(A[], n)
  max = A[0]
  for i = 1 to n-1
      if A[i] > max
          max = A[i]
  return max

의사코드(Pseudocode)는 특정 프로그래밍 언어가 아니라, 알고리즘의 논리를 명확히 표현하기 위한 약속된 표기법이다. CLRS 교재는 자체적인 의사코드 스타일로 알고리즘을 기술한다.

순서도:

flowchart TD
    S(["시작"]) --> I["max = A[0], i = 1"]
    I --> C1{"i < n ?"}
    C1 -->|"아니오"| R["return max"]
    C1 -->|"예"| C2{"A[i] > max ?"}
    C2 -->|"예"| U["max = A[i]"]
    C2 -->|"아니오"| N["i = i + 1"]
    U --> N
    N --> C1
Loading

그림 4. 최댓값 찾기의 순서도

순서도는 단순한 알고리즘에는 직관적이지만, 대규모 프로그램에서는 복잡해지므로 현대 교과서에서는 의사코드가 주로 사용된다.

1.5 알고리즘 분류

아래 분류는 알고리즘 설계 전략 전체를 한눈에 보인 것이며, 분할 정복은 4주차, 그리디 알고리즘은 5주차, 동적 프로그래밍은 6주차, 근사 알고리즘은 13~14주차에서 자세히 다룬다.

문제 해결 전략에 따라 알고리즘을 다음 6가지 주요 유형으로 나눈다.

유형 핵심 아이디어
분할 정복
(Divide and Conquer)
부분 문제로 나누기 → 각각 해결 → 결과 합치기.
예: 병합 정렬(Merge Sort)은 배열을 반으로 나누고, 각 반쪽을 정렬한 뒤, 정렬된 반쪽을 합친다.
그리디
(Greedy)
매 단계에서 지역적으로 최적인 선택.
예: Dijkstra 알고리즘은 항상 가장 짧은 알려진 경로를 확장하여 그래프의 모든 정점에 도달한다.
동적 프로그래밍
(Dynamic Programming)
부분 문제를 풀고, 결과를 저장하여 재사용.
예: 배낭 문제(Knapsack Problem)는 무게와 가치가 있는 물건들이 주어졌을 때, 가방에 넣을 수 있는 가장 가치 있는 조합을 찾는다.
근사
(Approximation)
NP-Hard 문제에 대한 근사적 최적 해.
예: 외판원 문제(TSP)에서 정확한 해를 구하기엔 비용이 너무 클 때, 모든 도시를 방문하는 거의 최단 경로를 찾는다.
백트래킹
(Backtracking)
모든 가능성을 탐색하되, 불가능한 가지를 가지치기(pruning).
예: N-Queen 문제는 N x N 체스판에 N개의 퀸을 서로 공격하지 않도록 배치한다.
분기 한정
(Branch and Bound)
백트래킹과 유사하나, 한계값(bound)을 이용해 더 공격적으로 가지치기.
예: 배낭 문제(정확 해)에서 현재 최적보다 나아질 수 없는 가지를 잘라내어 최적 물건 선택을 찾는다.

표 4. 문제 해결 전략에 따른 알고리즘의 6가지 유형

핵심: 이 6가지 분류는 과목 전체를 관통하는 핵심 프레임워크이다. 이 중 분할 정복, 그리디 알고리즘, 동적 프로그래밍이 가장 집중적으로 다루는 3대 핵심 전략이다.

분할 정복 (Divide and Conquer):

큰 문제를 더 작은 부분 문제로 나누고, 각각을 재귀적으로 해결한 뒤, 결과를 합친다. 장점: 문제 구조가 자연스럽게 재귀적일 때 효과적이다. 예시: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary Search).

그림 5. 수열 5, 2, 4, 7, 1, 3, 2, 6을 병합 정렬하는 과정

그림 5. 수열 5, 2, 4, 7, 1, 3, 2, 6을 병합 정렬하는 과정

분할 정복은 항상 다음 3단계로 구성되며, 4주차에서 자세히 다룬다.

  1. 분할(Divide): 문제를 더 작은 부분 문제로 나눈다
  2. 정복(Conquer): 각 부분 문제를 재귀적으로 해결한다 (충분히 작으면 직접 해결)
  3. 결합(Combine): 부분 문제들의 해를 합쳐 원래 문제의 해를 만든다

병합 정렬에서 분할은 배열을 반으로 나누는 것이고, 정복은 각 반쪽을 재귀적으로 정렬하는 것이며, 결합은 두 정렬된 반쪽을 병합(merge)하는 것이다.

그리디 알고리즘 (Greedy Algorithms):

매 단계에서 지금 당장 가장 좋아 보이는 선택을 한다. 항상 전역 최적해를 보장하는 것은 아니지만, 특정 조건 하에서는 보장된다. 예시: 최소 신장 트리 (Kruskal, Prim), Dijkstra 최단 경로, Huffman 코딩.

그리디 알고리즘이 최적해를 보장하려면 두 가지 조건이 필요하다.

  1. 그리디 선택 성질(Greedy Choice Property): 지역적으로 최적인 선택이 전역적 최적해로 이어진다
  2. 최적 부분 구조(Optimal Substructure): 문제의 최적해가 부분 문제의 최적해를 포함한다

이 조건이 만족되지 않으면 그리디 알고리즘은 최적이 아닌 해를 줄 수 있다. 5~6주차에서 엄밀하게 다룬다.

동적 프로그래밍 (DP):

문제를 부분 문제로 나누되(분할 정복처럼), 겹치는 부분 문제의 결과를 저장하고 재사용한다.

핵심 조건:

  • 겹치는 부분 문제 (Overlapping Subproblems)
  • 최적 부분 구조 (Optimal Substructure)

예시: 피보나치 수열, 최장 공통 부분 수열 (LCS), 배낭 문제 (Knapsack).

DP vs 분할 정복: 분할 정복의 부분 문제는 독립적이고, DP의 부분 문제는 겹친다(overlap).

피보나치로 차이를 살펴보면 다음과 같다.

  • 분할 정복: fib(5) → fib(4) + fib(3), fib(4) → fib(3) + fib(2)처럼 전개되며, 여기서 fib(3)이 중복 계산된다. 시간 복잡도는 $O(2^n)$이다.
  • DP: fib(1), fib(2)부터 차례로 계산하여 테이블에 저장하고 재사용한다. 중복 계산이 없어 O(n)이다.

근사, 백트래킹, 분기 한정: 표 4의 세 전략 가운데 근사 알고리즘은 정확한 해가 너무 비싼 NP-Hard 문제에서 최적성을 속도와 바꾸며 TSP 근사와 정점 커버에 쓰인다. 백트래킹은 N-Queen과 미로 탐색에, 분기 한정은 TSP와 배낭 문제의 정확 해에 쓰인다.

참고: NP-Hard 문제는 NP에 속하는 모든 문제가 다항 시간에 환원되는 문제로, 현재까지 다항 시간에 푸는 알고리즘이 알려져 있지 않다. 예를 들어, 외판원 문제(TSP)는 n이 커지면 모든 경우의 수를 확인하는 것이 사실상 불가능하다. 13주차에서 자세히 다룬다.

백트래킹과 분기 한정의 핵심 차이는 다음과 같다.

  • 백트래킹: 이 방향으로 가면 해가 존재할 수 있는가를 검사한다(가능성 검사).
  • 분기 한정: 이 방향으로 가면 현재까지의 최적해보다 나아질 수 있는가를 검사한다(최적성 검사).

분기 한정은 상한 또는 하한을 계산하여, 현재 최적해보다 나아질 가능성이 없는 가지를 통째로 잘라낸다.

기타 분류:

  • 문제 영역별: 정렬, 그래프, 계산 기하학
  • 컴퓨팅 환경별: 병렬, 분산, 양자
  • 기타: 인공지능과 기계학습 알고리즘


2. 시간 복잡도

2.1 시간 복잡도의 개념

시간 복잡도는 입력 크기 $n$에 대한 기본 연산 횟수를 함수로 표현한 것이다. 기본 연산이란 비교, 읽기, 쓰기, 산술 연산 등 상수 시간이 걸리는 단순한 연산을 말한다.

이 연산 횟수 계산은 RAM(Random Access Machine) 모델을 전제로 한다. RAM 모델에서는 각 기본 연산(산술, 비교, 메모리 접근)이 정확히 1단위 시간이 소요된다.

예시: $n$장의 카드에서 최댓값 찾기

  • 순차 스캔: 각 카드를 현재 최댓값과 비교한다.
  • 비교 횟수: $n - 1$
  • 시간 복잡도: $T(n) = n - 1$

핵심: 시간 복잡도를 구할 때 핵심은 입력 크기 n에 대해 기본 연산이 몇 번 수행되는가를 세는 것이다. 실제 실행 시간(초)이 아니라 연산 횟수를 추상적으로 계산한다. 이렇게 하면 컴퓨터 성능에 관계없이 알고리즘의 본질적인 효율성을 비교할 수 있다.

2.2 실행 시간 예시

예시 1: O(1)

sample1(A[], n)
    k = n / 2
    return A[k]

나눗셈 1번과 배열 접근 1번만 수행하므로 $n$에 관계없이 상수 시간이다.

예시 2: O(n)

sample2(A[], n)
    sum = 0
    for i = 1 to n
        sum = sum + A[i]
    return sum

루프가 $n$번 실행되므로 선형 시간이다.

예시 3: O(n²)

sample3(A[], n)
    sum = 0
    for i = 1 to n
        for j = 1 to n
            sum = sum + A[i] * A[j]
    return sum

중첩 루프가 각각 $n$번 실행되므로 $n \times n$, 즉 이차 시간(quadratic time) 이다.

중첩 루프의 시간 복잡도를 구하는 기본 원칙은 다음과 같다. 안쪽 루프의 반복 횟수가 바깥쪽 루프와 무관하게 일정하면, 전체 반복 횟수는 안쪽 루프의 반복 횟수 × 바깥쪽 루프의 반복 횟수이다. 여기서는 n × n = n²이다. 루프가 3중이면 O(n³)이 된다.

예시 4: O(n²) (삼각형 루프)

sample4(A[], n)
    sum = 0
    for i = 1 to n-1
        for j = i+1 to n
            sum = sum + A[i] * A[j]
    return sum

안쪽 루프는 총 $(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$번 실행되므로 여전히 $O(n^2)$이다.

$1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}$는 등차급수의 합 공식이다. Big-O에서는 최고차항만 남기고 계수를 무시하므로 O(n²)이 된다. 이런 삼각형 형태의 이중 루프는 매우 자주 등장한다(예: 중복 검사, 모든 쌍 비교).

예시 5: O(n) (재귀)

factorial(n)
    if n == 1 return 1
    return n * factorial(n - 1)

재귀 깊이가 $n$이므로 선형 시간이다.

재귀 함수의 시간 복잡도는 재귀 호출이 총 몇 번 발생하는지로 판단한다. factorial(n)은 정확히 n번 호출되므로 O(n)이다. 각 호출에서 하는 일(곱셈 1번)이 O(1)이므로, 총 시간 복잡도는 O(n) × O(1) = O(n)이다.

2.3 복잡도 분석의 유형

유형 의미
최악의 경우(Worst-case) 상한이며, 어떤 입력이든 이보다 오래 걸리지 않음을 보장한다
평균의 경우(Average-case) 확률 분포(보통 균등 분포)에서의 기대 시간
최선의 경우(Best-case) 가장 빠른 실행이며, 최적 알고리즘을 찾는 데 사용한다
분할 상환(Amortized) 일련의 연산에 대한 연산당 평균 비용

표 5. 복잡도 분석의 네 가지 유형

분할 상환 분석은 평균 분석과 다르다. 일련의 연산 시퀀스에 대한 최악의 총 비용을 구한 뒤, 연산 횟수로 나눈 것이다. 예를 들어, 동적 배열은 가끔 크기를 재할당(비용이 큼)해야 하지만, 대부분의 삽입은 저렴하므로 삽입당 분할 상환 비용은 O(1)이다.

실무에서는 최악의 경우 분석이 가장 일반적으로 사용된다.

핵심: 최악의 경우를 주로 사용하는 이유는 보장(guarantee) 을 제공하기 때문이다. 이 알고리즘은 어떤 입력이 와도 n² 시간을 넘지 않는다는 식의 확실한 약속이 된다. 반면 평균 분석은 입력 분포를 가정한 기댓값이므로 개별 입력에 대한 보장은 아니다. 예를 들어, 퀵 정렬은 평균 O(n log n)이지만 최악 O(n²)이다.

통근 시간 비유:

그림 6. 서울 지하철

그림 6. 서울 지하철

시나리오: 집 → 역 (6분) → 지하철 (20분) → 강의실 (10분)

경우 시간 설명
최선 36분 열차가 바로 온 경우
최악 40분 열차가 방금 떠나 4분 대기한 경우
평균 38분 평균 대기 약 2분

표 6. 통근 시간의 최선, 최악, 평균의 경우

알고리즘 분석도 같은 방식으로 생각하며, 최악의 경우가 보장을 제공한다.



3. 점근적 표기법

3.1 점근적 표기법을 쓰는 이유

2절에서는 $T(n) = n-1$이나 $T(n) = n(n-1)/2$ 같은 정확한 연산 횟수를 계산하였다. 하지만 이런 정확한 횟수는 구현 세부 사항에 따라 달라진다(루프가 0부터 시작하는가 1부터 시작하는가? 마지막 비교를 세는가?). 점근적 표기법은 이런 무관한 세부 사항을 제거하고, 진정으로 중요한 것, 즉 $n$이 커질 때 실행 시간이 어떻게 증가(scale) 하는지에 집중하게 해 준다.

그림 7. Θ, O, Ω 표기법의 그래프 표현

그림 7. Θ, O, Ω 표기법의 그래프 표현

  • 시간 복잡도는 $n$의 함수이다(보통 여러 항이 있는 다항식).
  • $n$이 커지면 지배적인 항(dominant term) 만 중요하다.
  • 점근적 표기법은 증가율(growth rate)에 초점을 맞춰 표현을 단순화한다.
표기법 의미 직관적 해석
$O$ (Big-O) 상한 최대 이 정도로 증가
$\Omega$ (Big-Omega) 하한 최소 이 정도로 증가
$\Theta$ (Theta) 엄밀한 한계 정확한 증가율

표 7. 세 가지 점근적 표기법의 의미

핵심: 점근적(asymptotic) 이란 n이 무한히 커질 때의 행동을 뜻한다. 예를 들어 $3n^2 + 100n + 5000$에서 n이 1,000,000이면 $3n^2 = 3 \times 10^{12}$이고 $100n = 10^8$이므로, $100n$은 $3n^2$에 비해 무시할 수 있을 만큼 작다. 그래서 최고차항만 남기고 나머지는 무시한다.

3.2 Big-O 표기법

공식 정의:

$O(g(n))$은 $g(n)$보다 최대 같은 속도로 증가하는 함수들의 집합이다.

$$O(g(n)) = \{ f(n) \mid \exists\, c > 0,\; n_0 \geq 0 \;\text{s.t.}\; \forall\, n \geq n_0,\; f(n) \leq c \cdot g(n) \}$$
  • $g(n)$은 $f(n)$의 점근적 상한(asymptotic upper bound) 이다.
  • 관례: 기술적으로는 $f(n) \in O(g(n))$이지만 $f(n) = O(g(n))$이라고 쓴다.

정의 읽는 법: "상수 $c &gt; 0$과 $n_0 \geq 0$이 존재하여, 모든 $n \geq n_0$에 대해 $f(n) \leq c \cdot g(n)$이다." 기호 $\exists$는 존재한다(there exists)를, $\forall$는 모든(for all)을 의미한다.

직관적 의미: $f(n) = O(g(n))$은 $f$가 $g$보다 더 빠르게 증가하지 않는다는 뜻이다(상수 배율 무시).

정의를 풀어 설명하면, 충분히 큰 n(n ≥ n₀)부터는 f(n)이 항상 c × g(n) 이하라는 뜻이다. 여기서 c와 n₀는 적절히 찾아야 하는 상수이며, 어떤 함수가 O(g(n))에 속함을 증명하려면 이 조건을 만족하는 c와 n₀를 구체적으로 찾아 제시하면 된다.

증명 예시: $f(n) = 2n^2 - 8n + 3 = O(n^2)$

$n \geq n_0$인 모든 $n$에 대해 $2n^2 - 8n + 3 \leq c \cdot n^2$을 만족하는 상수 $c &gt; 0$과 $n_0 \geq 0$을 찾아야 한다.

$c = 5$를 선택한다.

$$2n^2 - 8n + 3 \leq 5n^2 \quad \text{(모든 } n \geq 1 \text{에서)}$$

이를 정리하면 $-3n^2 - 8n + 3 \leq 0$이고, 이는 $n \geq 1$에서 성립한다.

전개 과정은 다음과 같다. $2n^2 - 8n + 3 \leq 5n^2$의 양변에서 $5n^2$을 빼면 $-3n^2 - 8n + 3 \leq 0$이다. $n \geq 1$이면 $-3n^2 \leq -3$이고 $-8n \leq -8$이므로 좌변은 $-3 - 8 + 3 = -8$ 이하이고, 따라서 0 이하이다. n이 커질수록 $-3n^2$이 지배하여 더욱 음수가 되므로 항상 성립한다.

따라서 $c = 5$, $n_0 = 1$로 $f(n) = O(n^2)$이다. $\square$

참고: c를 고르는 방법. 최고차항 계수가 양수인 다항식 $a_k n^k + a_{k-1} n^{k-1} + \cdots + a_0$에 대해 모든 계수의 절댓값 합 $|a_k| + |a_{k-1}| + \cdots + |a_0|$을 c로 잡으면 $n_0 = 1$에서 항상 성립한다. $n \geq 1$이면 각 항이 $a_i n^i \leq |a_i| n^k$를 만족하기 때문이다. 예: $2n^2 - 8n + 3$이면 $c = 2 + 8 + 3 = 13$, $n_0 = 1$이다.

$O(n^2)$에 포함되는 함수:

  • $3n^2 + 2n$ ✓, $7n^2 - 100n$ ✓, $n \log n + 5n$ ✓, $3n$ ✓

$O(n^2)$에 속하지 않는 함수:

  • $n^3$ ✗, $3^n$ ✗

모범 사례: 가능한 한 촘촘하게(tight) 쓴다. $n \log n + 5n = O(n \log n)$이라고 쓰고, $O(n^2)$이라고 쓰지 않는다. 느슨한 한계는 정보의 손실을 의미한다.

이 알고리즘은 O(n²)이라는 서술과 이 알고리즘은 O(n log n)이라는 서술은 둘 다 참일 수 있지만, O(n log n)이 더 유용한 정보이다. 이 사과는 100원 이하라는 정보보다 이 사과는 50원 이하라는 정보가 더 유용한 것과 같다.

더 많은 Big-O 예시:

수식 Big-O 이유
$3n + 2$ $O(n)$ $3n+2 \leq 4n$ ($n \geq 2$일 때)
$100n + 6$ $O(n)$ $100n+6 \leq 101n$ ($n \geq 10$일 때)
$10n^2 + 4n + 2$ $O(n^2)$ $10n^2+4n+2 \leq 11n^2$ ($n \geq 5$일 때)
$6 \cdot 2^n + n^2$ $O(2^n)$ $6 \cdot 2^n + n^2 \leq 7 \cdot 2^n$ ($n \geq 4$일 때)

표 8. Big-O 표기의 예와 근거

3.3 Big-Omega 표기법

공식 정의:

$\Omega(g(n))$은 $g(n)$보다 최소 같은 속도로 증가하는 함수들의 집합이다.

$$\Omega(g(n)) = \{ f(n) \mid \exists\, c > 0,\; n_0 \geq 0 \;\text{s.t.}\; \forall\, n \geq n_0,\; f(n) \geq c \cdot g(n) \}$$
  • $g(n)$은 $f(n)$의 점근적 하한(asymptotic lower bound) 이다.
  • Big-O와 대칭적이다.

직관적 의미: $f(n) = \Omega(g(n))$은 $f$가 $g$보다 더 느리게 증가하지 않는다는 뜻이다.

예시:

수식 Big-Omega 이유
$3n + 2$ $\Omega(n)$ $3n+2 \geq 3n$ ($n \geq 1$일 때)
$100n + 6$ $\Omega(n)$ $100n+6 \geq 100n$ ($n \geq 1$일 때)
$10n^2 + 4n + 2$ $\Omega(n^2)$ $10n^2+4n+2 \geq n^2$ ($n \geq 1$일 때)
$6 \cdot 2^n + n^2$ $\Omega(2^n)$ $6 \cdot 2^n + n^2 \geq 2^n$ ($n \geq 1$일 때)

표 9. Big-Omega 표기의 예와 근거

모범 사례: 가능한 한 촘촘하게 쓴다. $n \log n + 5n = \Omega(n \log n)$이라고 쓰고, $\Omega(n)$이라고 쓰지 않는다.

증명 예시: $10n^2 + 4n + 2 = \Omega(n^2)$

$c = 10$, $n_0 = 1$로 선택한다. 그러면 모든 $n \geq 1$에 대해 $10n^2 + 4n + 2 \geq 10n^2 \geq c \cdot n^2$이다. $\square$

3.4 Theta 표기법

공식 정의:

$\Theta(g(n))$은 $g(n)$과 같은 속도로 증가하는 함수들의 집합이다.

$$\Theta(g(n)) = O(g(n)) \;\cap\; \Omega(g(n))$$ $$\Theta(g(n)) = \{ f(n) \mid \exists\, c_1, c_2 > 0,\; n_0 \geq 0 \;\text{s.t.}\; \forall\, n \geq n_0,\; c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \}$$

직관적 의미: $f(n) = \Theta(g(n))$은 $f$와 $g$가 (상수 배율 차이를 제외하면) 같은 속도로 증가한다는 뜻이다.

핵심: Θ는 가장 정확한 표기법이다.

  • O(n²): 이 알고리즘은 최대 n² 수준이다(더 빠를 수도 있다).
  • Ω(n²): 이 알고리즘은 최소 n² 수준이다(더 느릴 수도 있다).
  • Θ(n²): 이 알고리즘은 정확히 n² 수준이다.

예시:

수식 Theta
$3n + 2$ $\Theta(n)$: $3n \leq 3n+2 \leq 4n$ ($n \geq 2$일 때)
$10n^2 + 4n + 2$ $\Theta(n^2)$
$6 \cdot 2^n + n^2$ $\Theta(2^n)$

표 10. Theta 표기의 예

반례: $2n^2 + 3n + 5 \neq \Theta(n^3)$이고 $2n^2 + 3n + 5 \neq \Theta(n)$이다. Theta는 상한과 하한이 모두 일치해야 하기 때문이다.

증명 예시: $3n + 2 = \Theta(n)$

상한: $3n + 2 \leq 5n$ ($n \geq 1$일 때, $c_2 = 5$). 하한: $3n + 2 \geq 3n$ ($n \geq 0$일 때, $c_1 = 3$). 따라서 $c_1 = 3$, $c_2 = 5$, $n_0 = 1$이다. $\square$

3.5 일반적인 복잡도 분류

표기법 이름 예시
$O(1)$ 상수 배열 인덱스 접근
$O(\log n)$ 로그 이진 탐색
$O(n)$ 선형 선형 탐색
$O(n \log n)$ 로그-선형 병합 정렬
$O(n^2)$ 이차 버블 정렬
$O(n^3)$ 삼차 행렬 곱셈 (단순)
$O(2^n)$ 지수 부분집합 완전 탐색

표 11. 일반적인 복잡도 분류와 예

계층구조: $O(1) \subset O(\log n) \subset O(n) \subset O(n \log n) \subset O(n^2) \subset O(n^3) \subset O(2^n)$

핵심: 실전에서의 감각은 다음과 같다.

  • O(1): 해시 테이블 조회(평균)이며, 즉시 끝난다.
  • O(log n): n=10억이어도 약 30번이므로 매우 빠르다.
  • O(n): n=10억이면 10억 번이며, 보통 수 초가 걸린다.
  • O(n log n): 대부분의 정렬이 해당하며, 실용적 한계이다.
  • O(n²): n=10만이면 100억 번이므로 느려지기 시작한다.
  • $O(2^n)$: n=40이면 약 1조 번이므로 사실상 불가능하다.

증가율 비교:

$n$ $\log n$ $n$ $n \log n$ $n^2$ $n^3$ $2^n$
10 3.3 10 33 100 1,000 1,024
100 6.6 100 664 10,000 $10^6$ $10^{30}$
1,000 10 1,000 10,000 $10^6$ $10^9$ $10^{301}$
$10^6$ 20 $10^6$ $2 \times 10^7$ $10^{12}$ $10^{18}$ -

표 12. 입력 크기에 따른 함수 값의 증가율 비교

다항식과 지수의 격차는 어마어마하다.

$2^{100} \approx 10^{30}$이고, $n = 1{,}000$이면 $2^n \approx 10^{301}$로 관측 가능한 우주의 원자 수(대략 $10^{80}$)를 크게 넘는다. $n = 100$이기만 해도 $2^n$은 상상할 수 없는 수준이다. 이것이 지수 시간 알고리즘은 실용적이지 않다는 말의 의미이다.

참고: 위 표에서 $\log n$은 $\log_2 n$이다. CS에서 별도 표기 없이 log라 쓰면 보통 밑(base)이 2이다. Big-O에서는 밑이 무엇이든 상관없다. $\log_a n = \frac{\log_b n}{\log_b a}$이므로 밑의 변환은 상수 배율일 뿐이고, Big-O에서 상수는 무시되기 때문이다.

3.6 효율적인 알고리즘이 중요한 이유

10억 개의 숫자 정렬:

알고리즘 $n$ = 1,000 $n$ = 1,000,000 $n$ = 1,000,000,000
$O(n^2)$ (PC) < 1초 약 3시간 약 300년
$O(n^2)$ (슈퍼컴퓨터) < 1초 약 1초 약 12일
$O(n \log n)$ (PC) < 1초 < 1초 약 5분
$O(n \log n)$ (슈퍼컴퓨터) < 1초 < 1초 < 1초

표 13. 알고리즘과 하드웨어에 따른 정렬 시간

PC는 초당 약 $10^8$번, 슈퍼컴퓨터는 초당 약 $10^{12}$번 연산한다고 가정한다.

핵심: 효율적인 알고리즘은 슈퍼컴퓨터보다 가치 있다.

더 좋은 하드웨어에 투자하는 것보다 더 나은 알고리즘에 투자하는 것이 훨씬 경제적이다.

입력이 충분히 크면 O(n²)을 슈퍼컴퓨터에서 돌리는 것보다 O(n log n)을 일반 PC에서 돌리는 것이 더 빠르며, n = 10억에서는 약 12일과 약 5분으로 약 3,300배 차이가 난다. 하드웨어는 상수 배율의 개선만 줄 수 있지만, 알고리즘 개선은 차수(order) 자체를 바꾼다.



4. 점화식

4.1 점화식의 개념

재귀 알고리즘을 분석할 때는 2절에서처럼 단순히 루프 반복 횟수를 셀 수 없다. 대신 실행 시간 $T(n)$을 더 작은 입력에서의 $T$ 값으로 표현하며, 이것이 점화식이다. 목표는 점화식을 풀어서 $O(n \log n)$ 같은 닫힌 형태의 표현을 얻는 것이다.

점화식(Recurrence Relation) 은 함수를 더 작은 입력에서의 값으로 표현한 식이다.

예시:

  • $a_n = a_{n-1} + 2$
  • $f(n) = n \cdot f(n-1)$: 팩토리얼
  • $f(n) = f(n-1) + f(n-2)$: 피보나치
  • $f(n) = f(n/2) + n$: 이진 감소

많은 재귀 알고리즘이 실행 시간에 대한 점화식을 자연스럽게 생성한다.

점화식은 재귀적으로 정의된 함수라고 생각하면 된다. 재귀 알고리즘은 실행 시간을 곧바로 닫힌 식으로 표현하기 어렵고, 대신 T(n)을 T(n/2)나 T(n-1) 등으로 표현하게 된다. 이렇게 세운 점화식을 풀어서 닫힌 형태(closed form)로 만드는 것이 목표이다.

병합 정렬의 점화식:

$$T(n) = 2T(n/2) + n$$

  • $2T(n/2)$: 반쪽에 대한 두 번의 재귀 호출
  • $n$: 병합 오버헤드 (선형 스캔)
  • $T(1) = 1$

병합 정렬의 동작은 다음과 같으며, 3주차와 4주차에서 자세히 다룬다.

  1. 배열 [5, 2, 4, 1, 3]을 반으로 나눈다: [5, 2] / [4, 1, 3]
  2. 각 반쪽을 재귀적으로 정렬한다: [2, 5] / [1, 3, 4]
  3. 두 정렬된 배열을 병합한다: [1, 2, 3, 4, 5]

병합(merge) 과정은 두 배열의 앞에서부터 비교하며 작은 것을 꺼내므로 O(n)이다. 점화식의 $n$이 바로 이 병합 비용이다.

점화식을 풀기 위한 세 가지 방법:

방법 아이디어
반복 대입법(Repeated Substitution) 점화식을 단계별로 전개하여 패턴을 찾는다
추측 후 검증(Guess and Verify) 형태를 추측한 뒤, 수학적 귀납법으로 증명한다
마스터 정리(Master Theorem) 특정 형태의 점화식에 공식을 직접 적용한다

표 14. 점화식을 푸는 세 가지 방법

4.2 방법 1: 반복 대입법

예시: $T(n) = T(n-1) + c$, $T(1) \leq c$

$$\begin{aligned} T(n) &= T(n-1) + c \\\ &= (T(n-2) + c) + c = T(n-2) + 2c \\\ &= T(n-3) + 3c \\\ &\;\;\vdots \\\ &= T(1) + (n-1)c \\\ &\leq c + (n-1)c = cn = O(n) \end{aligned}$$

이것은 팩토리얼의 점화식이며, 선형 시간이다.

반복 대입법의 핵심 전략은 T(n)에 점화식을 반복해서 대입하면서 패턴을 찾고, 그 패턴을 일반화하는 것이다. 위 예시에서 패턴은 k번 대입하면 T(n-k) + kc가 된다는 것이다. k = n-1을 대입하면 T(1) + (n-1)c가 된다.

병합 정렬에 적용: $T(n) = 2T(n/2) + n$, $T(1) = 1$

$n = 2^k$라 가정한다.

$$\begin{aligned} T(n) &= 2T(n/2) + n \\\ &= 2(2T(n/4) + n/2) + n = 4T(n/4) + 2n \\\ &= 8T(n/8) + 3n \\\ &\;\;\vdots \\\ &= 2^k T(n/2^k) + kn \\\ &= n \cdot T(1) + n \log_2 n \\\ &= n + n \log n = O(n \log n) \end{aligned}$$

전개 과정의 패턴은 다음과 같다.

  • 1번 대입: $2T(n/2) + n$ → 계수 2, 문제 크기 n/2
  • 2번 대입: $4T(n/4) + 2n$ → 계수 4, 문제 크기 n/4
  • k번 대입: $2^k T(n/2^k) + kn$

$n = 2^k$이면 $k = \log_2 n$이고, $2^k = n$이므로 $n \cdot T(1) + n\log n$이 된다. $n = 2^k$라 가정하는 것은 계산을 깔끔하게 하기 위한 것이며, 일반적인 n에 대해서도 점근적으로 같은 결과가 성립한다.

4.3 방법 2: 추측 후 검증 (귀납법)

점화식: $T(n) = 2T(n/2) + n$

추측: $T(n) = O(n \log n)$, 즉 어떤 상수 $c &gt; 0$에 대해 $T(n) \leq cn \log n$이다.

[이산수학] 수학적 귀납법의 3단계는 다음과 같다.

  1. 기저 사례(Base Case): 가장 작은 경우에 명제가 참임을 보인다
  2. 귀납 가정(Inductive Hypothesis): n = k일 때 명제가 참이라고 가정한다
  3. 귀납 단계(Inductive Step): n = k+1일 때도 참임을 보인다

이 세 단계를 완성하면 모든 자연수에 대해 명제가 참이 된다. 아래 증명처럼 n보다 작은 입력(예: n/2)에서 명제가 참이라고 가정하는 형태(강한 귀납법)도 같은 원리이며, 추측 후 검증법은 추측한 상한을 이 방식으로 증명한다.

수학적 귀납법으로 증명:

기저 사례: $T(2) = 2T(1) + 2 = 2(1) + 2 = 4$이다. $4 \leq c \cdot 2 \cdot \log_2(2) = 2c$가 필요하므로, $c \geq 2$이면 충분하다.

귀납 가정: $T(n/2) \leq c(n/2)\log(n/2)$라 가정한다.

귀납 단계:

$$\begin{aligned} T(n) &= 2T(n/2) + n \\\ &\leq 2 \cdot c(n/2)\log(n/2) + n \\\ &= cn\log n - cn\log 2 + n \\\ &= cn\log n + (-c\log 2 + 1)n \\\ &\leq cn\log n \quad \text{(} c \geq 1/\log 2 \text{일 때)} \end{aligned}$$

따라서 $T(n) = O(n \log n)$이다. $\square$

흔한 함정:

주의: 가정에서의 상수 $c$는 결론에서의 $c$와 동일해야 한다.

잘못된 증명 시도로, $T(n) = 2T(n/2) + 1$에 대해 $T(n) = O(n)$을 추측하면 다음과 같다.

$$T(n) \leq 2 \cdot c(n/2) + 1 = cn + 1$$

이것은 $cn + 1$이며, $\leq cn$이 아니다. 따라서 증명이 실패한다.

수정: 추측을 $T(n) \leq cn - 2$로 강화한다.

$$T(n) \leq 2(c(n/2) - 2) + 1 = cn - 4 + 1 = cn - 3 \leq cn - 2 \;\checkmark$$

흔한 실수: 귀납법 증명에서 가장 흔한 실수는 cn + (상수)를 얻고서 O(n)이므로 충분하다고 결론 내리는 것이다. 귀납법에서는 정확히 같은 형태($\leq cn$)를 보여야 한다. 해결법은 추측을 $cn - d$(적절한 상수 d)로 약간 줄여서 여유를 만드는 것이다.

상수 $d$를 체계적으로 결정하는 방법은 다음과 같다. 원래 증명에서 $T(n) \leq cn + 1$이 나왔는데 $\leq cn$이 필요하다. 추측을 $cn - d$로 놓고 귀납 단계를 전개하면 $T(n) \leq 2(c(n/2) - d) + 1 = cn - 2d + 1$이다. 이것이 $\leq cn - d$이려면 $-2d + 1 \leq -d$, 즉 $d \geq 1$이면 충분하다. 핵심은 초과분을 흡수할 수 있는 여유(slack)를 만드는 것이다.

4.4 방법 3: 마스터 정리

다음 형태의 점화식을 생각한다.

$$T(n) = aT(n/b) + f(n) \quad \text{(단, } a \geq 1, \; b > 1\text{)}$$

$h(n) = n^{\log_b a}$로 놓고, $f(n)$과 $h(n)$을 비교한다.

경우 조건 결과
Case 1 $f(n) = O(n^{\log_b a - \varepsilon})$ (어떤 $\varepsilon &gt; 0$) $T(n) = \Theta(n^{\log_b a})$
Case 2 $f(n) = \Theta(n^{\log_b a})$ $T(n) = \Theta(n^{\log_b a} \log n)$
Case 3 $f(n) = \Omega(n^{\log_b a + \varepsilon})$ (어떤 $\varepsilon &gt; 0$), 그리고 $af(n/b) \leq cf(n)$ (어떤 $c &lt; 1$) $T(n) = \Theta(f(n))$

표 15. 마스터 정리의 세 가지 경우

다항식적으로(polynomially) 더 작다 또는 크다는 다음을 뜻한다. $f(n) = O(n^{\log_b a - \varepsilon})$에서 $\varepsilon &gt; 0$이 존재해야 한다는 것은, f(n)이 $n^{\log_b a}$보다 $n^{\varepsilon}$ 배만큼 작아야 한다는 뜻이다. 예를 들어 $n^{\log_b a} = n$이고 $f(n) = n / \log n$이면, 이것은 n보다 작지만 다항식적으로 작지는 않다. 이런 경우 마스터 정리를 직접 적용할 수 없다.

핵심: 마스터 정리는 분할 정복 알고리즘의 점화식을 한 번에 풀어 주는 강력한 도구이다. 핵심은 간단하다.

  • $a$: 재귀 호출 횟수
  • $b$: 문제가 줄어드는 비율
  • $f(n)$: 분할과 결합에 드는 비용
  • $n^{\log_b a}$: 재귀 트리의 리프(leaf) 수준 비용

3가지 Case는 리프 비용이 이기는지(Case 1), 루트 비용이 이기는지(Case 3), 아니면 비기는지(Case 2)를 판단한다.

직관:

$$T(n) = aT(n/b) + f(n)$$

재귀 트리의 각 레벨이 작업을 수행한다. 어느 쪽이 지배하는가?

그림 8. 병합 정렬 점화식의 재귀 트리와 레벨별 비용

그림 8. 병합 정렬 점화식의 재귀 트리와 레벨별 비용

시나리오 승자 결과
리프가 지배 리프 작업 승 $T(n) = \Theta(n^{\log_b a})$
루트가 지배 루트 작업 승 $T(n) = \Theta(f(n))$
균형 레벨당 동일 $T(n) = \Theta(n^{\log_b a} \log n)$

표 16. 재귀 트리에서 지배하는 부분에 따른 결과

트리의 높이는 $\log_b n$이고, 각 레벨의 총 비용이 합산된다.

[자료구조] 재귀 트리(recursion tree)는 트리의 응용이다. 루트는 원래 문제, 각 내부 노드는 재귀 호출, 리프는 기저 사례이다. 트리의 높이가 $\log_b n$인 이유는, 각 레벨에서 문제 크기가 $1/b$로 줄어들기 때문이다(n → n/b → n/b² → … → 1).

예시:

예시 1: $T(n) = 2T(n/3) + c$

  • $a = 2$, $b = 3$, $h(n) = n^{\log_3 2} \approx n^{0.63}$, $f(n) = c = O(1)$
  • $f(n)$이 다항식적으로 더 작다 → Case 1
  • $T(n) = \Theta(n^{\log_3 2})$

예시 2: $T(n) = 2T(n/4) + n$

  • $a = 2$, $b = 4$, $h(n) = n^{\log_4 2} = n^{0.5} = \sqrt{n}$, $f(n) = n$
  • $f(n)$이 다항식적으로 더 크다 → Case 3
  • $T(n) = \Theta(n)$

예시 3: $T(n) = 2T(n/2) + n$

  • $a = 2$, $b = 2$, $h(n) = n^{\log_2 2} = n$, $f(n) = n$
  • $f(n) = \Theta(h(n))$ → Case 2
  • $T(n) = \Theta(n \log n)$

마스터 정리는 다음 순서로 적용한다.

  1. a, b, f(n)을 식별한다
  2. $n^{\log_b a}$를 계산한다
  3. f(n)과 $n^{\log_b a}$를 비교한다
  4. 해당하는 Case를 적용한다

예시 3은 바로 병합 정렬의 점화식이다. 마스터 정리를 쓰면 반복 대입이나 귀납법 없이 바로 Θ(n log n)을 얻을 수 있다.

정칙 조건(regularity condition)은 $f(n)$이 잘 행동하는(well-behaved) 함수임을 보장한다. 구체적으로, 재귀 트리의 각 레벨에서 수행되는 작업이 기하급수적으로 감소한다는 것이다. Case 3의 첫 조건을 만족하는 흔한 함수(다항식, 지수 함수)는 대부분 이 조건도 자동으로 만족한다.

Case 3의 검증: Case 3은 적용이 가장 까다롭다. 정칙 조건($af(n/b) \leq cf(n)$)까지 확인해야 하기 때문이다. 흔한 분할 정복 알고리즘의 점화식은 대부분 Case 1 또는 Case 2로 해결되므로, 우선 $n^{\log_b a}$를 계산하고 f(n)과 비교하는 데 집중하는 것이 효과적이다.



요약

개념 핵심 요약
알고리즘 문제 해결을 위한 단계별 절차이며, 정확성, 실행 가능성, 유한성, 효율성이 필수 속성이다.
유클리드 GCD 알려진 가장 오래된 알고리즘 중 하나(기원전 300년경)이며, GCD(A, B) = GCD(B, A mod B)를 반복 적용한다.
반복 vs 재귀 반복은 루프를, 재귀는 자기 호출을 쓰며, 결과는 같지만 재귀는 호출 스택을 사용한다.
알고리즘 표현 자연어, 의사코드(가장 일반적), 순서도로 표현한다.
알고리즘 분류 분할 정복, 그리디 알고리즘, DP, 근사, 백트래킹, 분기 한정으로 나누며, 3대 핵심은 분할 정복, 그리디 알고리즘, DP이다.
시간 복잡도 입력 크기 $n$에 대한 기본 연산 횟수이며, 실행 시간(초)이 아닌 추상적 연산 횟수로 계산한다.
복잡도 분석 유형 최악(가장 일반적이며 보장을 제공), 평균, 최선, 분할 상환으로 나눈다.
Big-O ($O$) 점근적 상한이며, 모든 $n \geq n_0$에서 $f(n) \leq c \cdot g(n)$인 상수 $c$, $n_0$가 존재함을 뜻한다.
Big-Omega ($\Omega$) 점근적 하한이며, 모든 $n \geq n_0$에서 $f(n) \geq c \cdot g(n)$인 상수 $c$, $n_0$가 존재함을 뜻한다.
Theta ($\Theta$) 엄밀한 한계이며, $O \cap \Omega$로 정확히 그 수준의 증가율을 뜻한다.
촘촘하게 쓰기 $O(n \log n)$이 $O(n^2)$보다 유용한 정보이며, 느슨한 한계는 정보 손실을 뜻한다.
복잡도 계층 $O(1) \subset O(\log n) \subset O(n) \subset O(n \log n) \subset O(n^2) \subset O(n^3) \subset O(2^n)$이다.
알고리즘 > 하드웨어 입력이 충분히 크면 O(n log n)을 PC에서 돌리는 것이 O(n²)를 슈퍼컴퓨터에서 돌리는 것보다 빠르다.
점화식 함수를 더 작은 입력에서의 값으로 표현한 식이며, 재귀 알고리즘의 시간 복잡도 분석에 사용한다.
반복 대입법 점화식을 반복 전개하여 패턴을 찾고 일반화한다.
추측 후 검증 형태를 추측한 뒤 수학적 귀납법으로 증명하며, 상수 c가 동일해야 한다는 함정에 주의한다.
마스터 정리 $T(n) = aT(n/b) + f(n)$에 적용하며, $n^{\log_b a}$와 $f(n)$을 비교하여 3가지 Case를 판단한다.


점검 문제

  1. 유클리드 GCD: GCD(48, 18)을 단계별로 추적하라. 몇 번의 반복이 필요한가?

    정답

    GCD(A, B) = GCD(B, A mod B)를 반복 적용한다: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. b == 0이 되면 재귀가 멈추고 남은 인자가 GCD가 된다. 따라서 3회의 반복(종료 호출까지 포함하면 4회 호출)이 필요하다. b가 빠르게 줄어들기 때문에 알고리즘이 매우 빠르며, Lamé의 정리에 의해 단계 수는 O(log min(a, b))이다.

  2. 연산 횟수 세기: for i in range(n): for j in range(i, n): count += 1 코드에서 count += 1은 몇 번 실행되는가? n의 함수로 표현하라.

    정답

    이것은 삼각형 이중 루프 패턴이다. 각 i = 0, 1, ..., n-1에 대해 안쪽 루프는 n - i번 실행되므로, 총합은 n + (n-1) + (n-2) + ... + 1 = n(n+1)/2이다. 점근적으로 이는 Θ(n²) 이다. 최고차항만 남기고 상수 인자 1/2은 무시한다. 삼각형 구조는 차수(order)를 줄이지는 못하고 상수 인자만 줄일 뿐이다.

  3. Big-O 증명: 적절한 c와 n₀를 찾아 5n³ + 2n² + 7 = O(n³)을 증명하라.

    정답

    모든 n ≥ n₀에 대해 5n³ + 2n² + 7 ≤ c · n³을 만족하는 c > 0과 n₀ ≥ 0을 찾으면 된다. 계수 절댓값의 합 기법을 사용해 c = 5 + 2 + 7 = 14, n₀ = 1로 잡는다. n ≥ 1일 때 5n³ + 2n² + 7 ≤ 5n³ + 2n³ + 7n³ = 14n³이 성립한다. 따라서 c = 14, n₀ = 1로 5n³ + 2n² + 7 = O(n³)이다. (c = 6, n₀ = 3 같은 더 촘촘한 값도 가능하다.)

  4. Big-Omega vs Big-O: n² = O(n³)은 참인가? n² = Ω(n³)은 참인가? 이유를 설명하라.

    정답

    n² = O(n³)은 참이다. n²은 n³보다 빠르게 증가하지 않으며, 모든 n ≥ 1에 대해 n² ≤ 1 · n³이다(c = 1, n₀ = 1). n² = Ω(n³)은 거짓이다. Big-Omega는 큰 n에서 n² ≥ c · n³을 만족하는 c > 0이 필요하지만, n²/n³ = 1/n → 0이므로 그런 상수는 존재하지 않는다. 즉, Big-O는 상한이라서 느슨할 수 있지만, Big-Omega는 실제 하한을 요구한다.

  5. Theta: f(n) = Θ(g(n))이면 f와 g의 관계에 대해 무엇을 알 수 있는가? f(n) = Θ(n²)과 f(n) = O(n³)이 동시에 참일 수 있는가?

    정답

    f(n) = Θ(g(n))은 f와 g가 상수 배율 차이를 제외하면 정확히 같은 속도로 증가한다는 뜻이다. 즉, f = O(g)이면서 동시에 f = Ω(g)이다. 그렇다, f(n) = Θ(n²)과 f(n) = O(n³)은 동시에 참일 수 있다. Θ-한계는 대응하는 O-한계를 자동으로 함의하며, Θ(n²)인 함수는 (느슨하게) O(n³)이기도 하다. Θ가 가장 엄밀한 표현이고, 대응되는 O는 항상 더 약하지만 모순되지 않는다.

  6. 마스터 정리: T(n) = 4T(n/2) + n에 마스터 정리를 적용하라. a, b, f(n)을 식별하고, $n^{\log_b a}$를 계산하고, 경우를 판정하고, T(n)을 구하라.

    정답

    a = 4, b = 2, f(n) = n이므로 $n^{\log_b a} = n^{\log_2 4} = n^2$이다. f(n) = n과 n²을 비교하면 n은 n²보다 다항식적으로 더 작다($\varepsilon = 1$을 택하면 $n = O(n^{2-1})$). 따라서 Case 1에 해당하며, $T(n) = \Theta(n^{\log_b a}) = \Theta(n^2)$이다. 직관적으로는 재귀 트리의 리프(leaf)가 지배한다. 리프가 n²개이고 각각 상수 작업을 수행하기 때문이다.

  7. 추측 후 검증: T(n) = T(n/2) + 1에 대해 T(n) = O(log n)을 추측하고 귀납법으로 검증하라. 기저 사례도 확인해야 한다.

    정답

    추측: 어떤 c > 0에 대해 T(n) ≤ c · log n. 기저 사례 (n = 2): T(2) = T(1) + 1. T(1) = 1이라 가정하면 T(2) = 2이고, 2 ≤ c · log₂ 2 = c이려면 c ≥ 2이다. 귀납 단계: T(n/2) ≤ c · log(n/2)라 가정하면, T(n) = T(n/2) + 1 ≤ c · log(n/2) + 1 = c · log n - c · log 2 + 1 ≤ c · log n은 c · log 2 ≥ 1, 즉 c ≥ 1/log 2일 때 성립한다. 밑이 2이면 log 2 = 1이므로 c ≥ 1이다(자연로그라면 c ≥ 1/ln 2 ≈ 1.44). c = 2로 두 조건을 모두 만족시키면 T(n) = O(log n)이 증명된다.

  8. 왜 중요한가? O(n log n) 알고리즘을 실행하는 PC와 O(n²) 알고리즘을 실행하는 슈퍼컴퓨터를 비교할 때, 어떤 입력 크기에서 PC가 이기는가?

    정답

    PC는 초당 10⁸번, 슈퍼컴퓨터는 초당 10¹²번 연산한다고 가정한다. 하드웨어 격차는 10,000배이다. PC가 이기는 조건은 n log n / 10⁸ < n² / 10¹², 즉 log n / n < 10⁻⁴이다. 대략 n > 200,000 정도에서 PC가 앞서기 시작한다. 입력이 수십만 개를 넘으면 PC의 더 좋은 알고리즘 차수가 슈퍼컴퓨터의 원시 속도를 이긴다. 핵심 메시지는 더 좋은 알고리즘이 더 좋은 기계를 이긴다는 것이다. 하드웨어는 상수 배율 개선만 주지만, 알고리즘의 차수는 증가 클래스 자체를 바꾸기 때문이다.