4 분 소요

본 포스트는 MIT Open Course 의 강의 자료에 대한 공부를 토대로 작성하였다.

Algorithms

우리가 real-life problem을 접할 때, 여러 개의 solutions 들이 존재함.

1. Algorithm Design / Approach

  • 복수 개의 알고리즘 설계 가능을 인식 -> 우수함을 입증

2. Algorithm Analysis

  • 평가기준을 확립, 과학적인 분석
    • Time Complexity : 알고리즘의 속도 비교, 우위성

Design & Analysis

알고리즘을 배우는 이유 -> “생각”

Solution for CS problems을 step-by-step으로 해결하는 과정 => 알고리즘

예제 1) Search 비교

1. Sequential Search

def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # target이 있는 인덱스 반환
    return -1  # 못 찾았을 경우

2. Binary Search

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid  # 찾으면 인덱스 반환
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # 못 찾았을 경우
  • 두 Search의 비교
알고리즘 시간복잡도 (최악) 정렬 필요 여부
Sequential Search O(n) 필요 없음
Binary Search O(log n) 필요함 (정렬된 배열)

같은 문제를 푸는 방법이라도 선택한 알고리즘에 따라 시간복잡도는 크게 달라질 수 있다.

예제 2) Fibonacci Sequence

\[F(0) = 0,\quad F(1) = 1\] \[F(n) = F(n - 1) + F(n - 2) \quad \text{(for } n \geq 2)\]

1. Recursion Algorithm

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
  • 단순하지만 비효율적
  • 시간복잡도
\[O(2^n)\]

2. Iteration Algorithm

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
  • 효율적이고 간단함.
  • 시간복잡도
\[O(n)\]

즉, Which is. he most efficient algortihm? 이 Algorithm Analysis인 것!

부록) MIT Algorithm Lec 01. Peak Finding

Peak Finding

1차원 Peak Finding

  • 정의
    • 피크 : 양 옆 값보다 크거나 같은 값
    • 예: b ≥ a 그리고 b ≥ c일 경우 b는 피크
  1. 순차 탐색 알고리즘
  • 왼쪽부터 오른쪽으로 순차적으로 비교
  • 시간복잡도 : O(n)(최악의 경우 모든 원소 탐색)
  1. Divide & Conquer 알고리즘
  • 중간 원소 a[n/2]를 기준으로 탐색
    • a[n/2] < a[n/2 - 1] → 왼쪽 절반 탐색
    • a[n/2] < a[n/2 + 1] → 오른쪽 절반 탐색
    • 그렇지 않으면 a[n/2]는 피크
  • 시간 복잡도 : O(log n)

2차원 Peak Finding

  • 정의

2D Peak : 상하좌우 값보다 크거나 같은 원소 \(a ≥ b, a ≥ c, a ≥ d, a ≥ e\)

  1. Attempt 1 : 1D 방식 확장
  • 중간 열 선택 j = m/2
  • 해당 열에서 1D Peak 탐색
  • 해당 행에서 다시 1D Peak 탐색 시도

문제 : 해당 행에 2D Peak 가 없을 수 있음.

  1. Attempt 2 : 개선된 분할 정복
  • 중간 열 선택 j = m/2
  • 그 열에서 전체 행 중 최댓값 위치 찾기 (i, j)
  • 좌우 값 (i, j-1)과 (i, j+1)과 비교
    • 더 큰 쪽이 있으면 해당 방향으로 절반 영역 재귀 탐색
    • 없다면 (i, j)는 2D 피크

  • 열이 하나만 남으면 해당 열에서 최댓값이 Peak

  • 시간 복잡도
\[T(n, m) = T(n, m/2) + Θ(n)\]

반복 횟수 = log m

따라서 \(Θ(n log m)\)

Time Complexity Analysis

알고리즘의 효율성은 입력 크기가 커질수록 어떻게 변하는지를 측정하는 것으로, 가장 중요한 것은 실행 시간, 그 외에 메모리 사용량도 고려 대상임.

  • Complexity Analysis

실제 CPU 사이클이나 언어에 따른 명령어 수는 분석에 부적절

기본 연산이 몇 번 수행되는지를 중심으로 시간 복잡도 분석 수행

입력 크기를 ‘n’ 이라 할 때, T(n)은 ‘n’ 크기의 입력에서 수행되는 기본 연산

시간 복잡도의 종류

  • T(n) : 모든 경우의 시간 복잡도 로 Every-case

  • W(n) : 최악의 경우 시간 복잡도 (Worst-case)

  • A(n) : 평균적인 경우 시간 복잡도 (Average-case)
  • B(n) : 최선의 경우 시간 복잡도 (Best-case)

알고리즘의 차수 (Order)

- Θ(n)이나 100n: 선형 시간 알고리즘

- Θ(n²)이나 0.01n²: 이차 시간 알고리즘

일반적으로 선형 시간 알고리즘이 이차 시간 알고리즘보다 효율적이다.

  • 5n²과 5n² + 100: 순수 이차 함수

  • 0.1n² + n + 100: 완전한 이차 함수

  • 낮은 차수 항은 무시하고 높은 차수 항만으로 복잡도 분류 가능

예: 0.1n³ + 10n² + 5n + 25 → Θ(n³)

점근적 표기법 정의

Big-O 표기

  • g(n) ∈ O(f(n)) 이면, 어떤 상수 c, N이 존재해서 모든 n ≥ N에 대해 g(n) ≤ c × f(n)

→ 점근적 상한 (Upper Bound)

Omega 표기

  • g(n) ∈ Ω(f(n)) 이면, 어떤 상수 c, N이 존재해서 모든 n ≥ N에 대해 g(n) ≥ c × f(n)

→ 점근적 하한 (Lower Bound)

Theta 표기

  • g(n) ∈ Θ(f(n)) 이면, 어떤 상수 c, d, N이 존재해서 모든 n ≥ N에 대해 c × f(n) ≤ g(n) ≤ d × f(n)

→ 정확한 차수 표현

부록2) MIT 6.042 Lec.13 - Asymptotics

### 점근적 표기법 요약

1. 틸다(~) 표기

  • f(x) ~ g(x)는 x → ∞일 때 f(x)/g(x) → 1을 의미

  • 같은 성장률을 가지는 함수

2. Big-O 표기

  • f(x) = O(g(x)) ⇨ |f(x)/g(x)|의 극한이 유한
  • 즉, f(x)는 g(x)보다 느리게 또는 같은 속도로 성장

  • 상한을 나타냄.

  • 표현방식
    • f(x) = O(g(x))
    • f(x) ∈ O(g(x)) (공식적인 집합 표현)
  • 예시
    • x = O(x²) → 맞음 (x/x² → 0)
    • x² = O(x) → 틀림 (x²/x → ∞)
    • 10⁶x = O(x²) → 맞음 (10⁶x/x² → 0)
    • x² = O(10⁶x) → 틀림 (x²/10⁶x → ∞)

3. Big-Omega 표기(Ω)

  • f(x) = Ω(g(x)) ⇨ f(x)/g(x)의 극한이 양수 이상
  • f(x)는 g(x)보다 같거나 빠르게 성장
  • 하한을 나타냄
  • 예시
    • x² = Ω(x)
    • 2^x = Ω(x²)
    • x/100 = Ω(100x + 25)

4. Theat 표기 (Θ)

  • f(x) = Θ(g(x)) ⇨ f(x)가 g(x)의 상한과 하한을 동시에 만족
  • 즉, Θ는 O와 Ω의 교집합
  • 예시
    • 10x³ - 20x + 1 = Θ(x³)
    • x/ln(x) ≠ Θ(x) (→ x/ln(x)는 느리게 성장)
    • x/100 = Θ(x) (상수 배는 무시)

5. Little-O (o) 표기

  • f(x) = o(g(x)) ⇨ f(x)/g(x) → 0
  • f(x)는 g(x)보다 엄격하게 느리게 성장
  • 예시
    • x/ln(x) = o(x)
    • x/100 ≠ o(x) → 상수배이므로 Θ(x)에 해당

6. 리틀 오메가 (ω) 표기

  • f(x) = ω(g(x)) ⇨ f(x)/g(x) → ∞
  • f(x)는 g(x)보다 엄격하게 빠르게 성장
  • 예시
    • x² = ω(x)
    • 4^x = ω(2^x)

주의사항

  • Big-O를 하한으로 사용하면 안 됨
  • f(x) ≥ O(g(x)) → 의미 없음 (잘못된 사용)

태그:

카테고리:

업데이트:

참고

Concurrency, Locks

8 분 소요

이번 포스트는 OS의 Concurrency와 Locks에 대해 다룬다.