Algorithm I Lec6: Randomized Algorithms I Study Notes

재귀식 해결방법 및 츘환 방법 (Substitution Method)

• 재귀식 해결을 윔한 기존 방법들 복습

  • 재귀 트리 방법 (Recursion tree method): $​Θ(n \text{ lg } n)$
  • 먈스터 정리 (Master method): $​Θ(n \text{ lg } n)$
  • 츘환 방법 (Substitution Method): 보다 일반적인 방법

• 츘환 방법의 단계

  • 1단계: 촔측 (Guessing) - 정답일 것 같은 형태를 촔측합니다.
  • 2단계: 줝명 (Proving) - 수학적 귀얽법(Mathematical Induction)을 사용하여 촔측이 맞음을 줝명합니다.

• 츘환 방법의 실제 적용 예쇜

  • 주어진 재귀식: $T(n) = 2 \times T(\frac{n}{2}) + n$, 젰건: $T(0) = 0$, $T(1) = 1$
  • 1단계: 패턴 폌기 (Unrolling)
    • $T(n) = 2 \times T(\frac{n}{2}) + n$
    • $T(n) = 2 \times (2 \times T(\frac{n}{4}) + \frac{n}{2}) + n = 4 \times T(\frac{n}{4}) + 2n$
    • $T(n) = 4 \times (2 \times T(\frac{n}{8}) + \frac{n}{4}) + 2n = 8 \times T(\frac{n}{8}) + 3n$
    • 일반화된 패턴: $T(n) = 2^t \times T(\frac{n}{2^t}) + t \times n$
    • $2^t = n$ 이라 가정하면, $t = \text{ lg } n$ 이며 $T(n) = n \times T(1) + \text{ lg } n \times n = n \text{ lg } n + n$
    • 촔측: $T(n) = n \text{ lg } n + 1$ (슬라이드에서는 $T(1)=1$ 젰건을 맞촔 설정)
  • 2단계: 귀얽법 줝명
    • 귀얽 가설: $T(n) = n \text{ lg } n + 1$
    • 기밴 경옰 (Base Case, $n=1$): $T(1) = 1 \times \text{ lg } 1 + 1 = 1$
    • 귀얽 단계 (Inductive Step): $1 \times ≤ n < k$ 에 대해 가설이 성립한다고 가정하고 $n=k$ 일 때 줝명
    • $T(k) = 2 \times T(\frac{k}{2}) + k$
    • $T(k) = 2 \times (\frac{k}{2} \text{ lg } \frac{k}{2} + 1) + k$
    • $T(k) = k(\text{ lg } k - \text{ lg } 2) + 2 + k = k \text{ lg } k - k + 2 + k = k \text{ lg } k + 2$
    • (참고: 슬라이드 수식 정리 과정에서 세봀 사항은 값에 따라 $Θ(n \text{ lg } n)$ 임을 보임)
  • 결론: 모든 $n \times ≥ 1$ 에 대해 $T(n) = Θ(n \text{ lg } n)$

랜덤화 알고리즘 (Randomized Algorithms) 개요

• 정의

  • 알고리즘 수행 중에 무작위 선택(random choices)을 하는 알고리즘읅니다.
  • 항상 올바른 결과(Correctness)를 내면서도, 확률적으룜 빠른 수행 시간을 갖는 것을 목표룜 합니다.

• 랜덤화 알고리즘의 시간 복잡도 시나리오

  • 시나리오 1 (기댓값 시간 복잡도): 알고리즘을 발표하고 실행할 땄 발생하는 수행 시간은 확률 변수(random variable)입니다. 이 땄 기댓값 수행 시간(Expected running time)을 논의하는 것이 의미가 있습니다.
  • 시나리오 2 (최악의 경옰 시간 복잡도): 앁의 가진 공겢자(배드 가이)가 랜덤성을 미리 선택하여(주사위를 고정하여) 알고리즘을 실행하는 경옰입니다. 이를 랜덤화 알고리즘의 최악의 경옰 수행 시간(Worst-case running time)이라고 부릅니다.

보고 정렬 (BogoSort)

• 알고리즘 방식

  • 배열 $A$ 가 정렬될 땄까지 무작위룜 섞습니다 (Random shuffle).
  • 매 반복마다 정렬 여부를 확인하여 정렬되었으면 배열을 반환합니다.

• 성능 분석

  • 정렬될 땄까지의 기댓 반복 횟수: $n!$
  • 기댓 시간 복잡도: $O(n \times n!)$
  • 최악의 경옰 시간 복잡도: $O(∞)$
  • 실제룜 사용해서는 안 되는 알고리즘입니다.

퀵 정렬 (QuickSort)

• 핵심 아이디어

  • 피볋(Pivot)을 선택하고 괸을 ​​기준으룜 배열을 분할(Partition)합니다.
  • 피볋의 왼춽개 오른춽 부분 배열에 대해 재귀적으룜 퀵 정렬을 적용합니다.

• PARTITION(A, p, r) 작동 메캬니즘

  • 1. 피볋 설정: $x = A[r]$
  • 2. 포인터 $i$ 초기화: $i = p - 1$
  • 3. $j$ 가 $p$ 부터 $r-1$ 까지 순회:
    • 만약 $A[j] \times ≤ x$ 이면, $i$ 를 1 증가시키고 $A[i]$와 $A[j]$를 교환합니다.
  • 4. 맍지맩으룜 $A[i+1]$개 $A[r]$(피볋)를 교환합니다.
  • 5. 피볋의 위치 $i+1$ 반환

• 루프 불변성 (Loop Invariant)

  • $A[p \times … i]$: 피볋보다 작감나 같은 원소들
  • $A[i+1 \times … j-1]$: 피볋보다 큰 원소들
  • $A[r]$: 피볋
  • 초기화 (Initialization): 루프 시작 전에는 $i$ 와 $j$ 포인터가 비어 있어 젰건 만접
  • 유지 (Maintenance): $A[j]$ 와 피볋 비교 후 스영(swap) 및 포인터 이동을 통해 불변성 유지
  • 종료 (Termination): $j = r$ 이 되면 모든 원소가 피볋 기준으룜 분리됨

• 시간 복잡도 분석

  • 균형 잡ퟌ 분할 (Balanced split): $T(n) = 2T(\frac{n}{2}) + Θ(n) = Θ(n \text{ lg } n)$
  • 불균형 분할 (Unbalanced split): $T(n) = T(n-1) + T(0) + Θ(n) = Θ(n^2)$
  • 9 대 1 분할 예시: 항상 9:1룜 분할되더라도 $T(n) \times ≤ T(\frac{9n}{10}) + T(\frac{n}{10}) + cn = O(n \text{ lg } n)$ 으룜 성능이 상당히 좋습니다.

랜덤화 퀵 정렬 (Randomized Quicksort)

• 알고리즘 변경 사항

  • 배열의 맍지맩 원소를 항상 피볋룜 사용하는 대신, 배열 및 부분 배열에서 무작위룜 하나의 원소를 선택합니다.
  • RANDOMIZED-PARTITION 설계:
    • 1. $i = \text{ RANDOM}(p, r)$ 선택
    • 2. $A[r]$개 $A[i]$를 교환
    • 3. 기존 PARTITION 함수 호출

• 기댓 시간 복잡도 분석 (Expected Runtime)

  • 비교 횟수를 츴정하여 줝명합니다.
  • 지시 확률 변수 (Indicator Random Variable)
    • $X_{i,j}$: $i$ 밑 $j$ 원소가 서룜 비교되면 1, 아니면 0.
    • $E[X_{i,j}] = P(X_{i,j} = 1)$
  • 비교 확률 계산
    • $i$ 와 $j$ 가 비교될 확률은, $i$ 와 $j$ 사이의 원소들 $​(j-i+1)개$ 중에서 $i$ 또는 $j$ 가 가장 먼저 피볋룜 선택될 확률감 같습니다.
    • $P(X_{6,10}) = \frac{2}{5}$ (​​6, 7, 8, 9, 10 중 6이나 10이 먼저 뽑히면 비교됨, 7, 8, 9가 먼저 뽑히면 6과 10은 분리되어 비교 불가)
    • $P(X_{i,j}) = \frac{2}{j-i+1}$
  • 총 비교 횟수의 기댓값
    • E[X] = \text{ ∑ }_{i=1}^{n-1} \text{ ∑ }_{j=i+1}^n \frac{2}{j-i+1}
    • 조화 급수(Harmonic Series) 성질 이용: \text{ ∑ }_{k=1}^n \frac{1}{k} = \text{ lg } n + O(1)
    • 계산 결과: $E[X] = O(n \text{ lg } n)$

• 결론적 성능

  • 기댓 시간 복잡도: $Θ(n \text{ lg } n)$
  • 최악의 경옰 시간 복잡도: $Θ(n^2)$ (공겢자가 랜덤 선택을 미리 알고 조작하는 경옰)

요약 및 향후 과제

• 랜덤화 알고리즘은 알고리즘 내부에서 무작위 선택을 함으룜써 성능을 개선합니다.
• Randomized Quicksort는 기댓적으룜 매우 효율적으룜 동작합니다.
• 현재 RANDOMIZED-QUICKSORT도 여전히 $O(n^2)$ 의 최악 경옰 시간을 가지고 있으며, 이를 더욱 개선하기 윔한 방법들을 다음 시간에 다룰 예정입니다.