algo_lec3

 

알고리즘 분석 (Part 2)

---

 

Practice 1 – Big-O Notation

• 5n2=O(n2)5n^2 = O(n^2): 참, c=6,n0=1c = 6, n_0 = 1
• 5n2+3=O(n2)5n^2 + 3 = O(n^2): 참, c=6,n0=2c = 6, n_0 = 2
• n3=O(n2)n^3 = O(n^2)?: 거짓. n≤cn \le c 가 항상 성립할 수 없기 때문

---

Practice 2 – Big-Omega Notation

• 5n2=Ω(n2)5n^2 = \Omega(n^2): 참, c=4,n0=1c = 4, n_0 = 1
• 5n2+3=Ω(n2)5n^2 + 3 = \Omega(n^2): 참, c=1,n0=1c = 1, n_0 = 1
• n=Ω(n2)n = \Omega(n^2)?: 거짓. n≥cn2n \ge c n^2 를 만족하는 c는 없음

---

Big-O 복습

• 점근적 상한 (asymptotic upper bound)
• 예: n^2 + n, 2nlog⁡n+3n ∈ O(n^2)

---

Big-Omega 복습

• 점근적 하한 (asymptotic lower bound)
• 예: n^2 + n, 5n^2 + 15 ∈ Ω(n^2)

---

Big-Theta 복습

• 정확한 점근적 경계 (exact bound)
• Θ(f(n))=O(f(n))∩Ω(f(n))
• 예: 5n^2 + 15 ∈ Θ(n^2)

---

시간복잡도 예시 – 선형 탐색 복습

def search(arr, x):
    for index, value in enumerate(arr):
        if value == x:
            return index
    return -1
    
if __name__ == '__main__':
    arr = [1, 10, 30, 15]
    x = 30

    # Function call
    print(x, "is present at index", search(arr, x))

• Worst-case (W(n)): 타겟이 없거나 마지막 → O(n)
• Average-case (A(n)):
  • 총 비교횟수: (1+2+...+n) + n = n(n+1) / 2+n
  • 평균: A(n) = (n(n+1)/2+n) / (n+1)=n/2 = O(n)

---

Amortized Analysis – Accounting Method 복습

• push: $2 지불 → $1은 실제 비용, $1은 계좌에 저장
• pop: $0 지불 → 계좌에서 $1 차감
• multipop: pop과 동일
• 모든 연산의 평균 비용: O(1)

---

n회 수행 시 Amortized Time 복습

연산 Amortized 시간복잡도

push	O(n)
pop	O(n)
multipop	O(n)

 

→ 전체 비용은 O(n) → 개별 연산 평균 O(1)

---

Amortized Analysis – Potential Method

• 잠재 에너지(Φ)는 자료구조에 저장된 에너지
• 연산이 D₀ → D₁로 구조를 바꿀 때: Amortized Cost=real cost + Φ(D1) − Φ(D0)
• 스택에서 Φ(D) = 항목 수로 정의

예시:

• push: 실제 비용 1, Φ증가 1 → 총 2 = O(1)
• pop: 실제 비용 1, Φ감소 -1 → 총 0 = O(1)
• multipop(k): 실제 비용 min(k, s), Φ감소 동일 → 총 0 = O(1)

→ 평균적으로 모든 연산이 O(1)

---

공간복잡도 (Space Complexity)

• 저장 공간은 다음으로 구성:
  • 명령어, 상수, 변수
  • 입력 데이터
  • 추가 작업 공간 (자료구조 등)
• 입력이 배열로 주어지면 추가 공간만 분석
• 그래프처럼 표현 방식이 다양할 경우, 입력 + 추가 공간 모두 분석
• Worst-case, Average-case 공간복잡도 분석 가능

---

Divide and Conquer (분할 정복)

• 큰 문제를 작게 나누고, 각 문제를 해결 후 결과를 병합
• Top-down 방식
• 단계: Divide → Conquer → Combine

재귀관계 표현

---

예제 1: Binary Search

• 정렬된 배열에서 이진 탐색
• T(n) = T(n/2) + 1
• 풀이는 다음과 같이 전개됨

• 결정 트리의 깊이로 나타낼 수 있음
• 최악 비교 횟수는 ≥ log⁡2(n+1)

---

예제 2: 최대값 찾기 Find the maximum (findMax)

def findMax(arr, start, end):
    if start == end:
        return arr[start]
    mid = (start + end) // 2
    lmax = findMax(arr, start, mid)
    rmax = findMax(arr, mid+1, end)
    return max(lmax, rmax)

• 재귀 관계

---

예제 3: 곱셈 알고리즘

3-1. 반복적 곱셈

재귀 곱셈 알고리즘( multiply(x, y) )의 실행 과정

def multiply(x, y):
    if y == 0:
        return 0
    z = multiply(x, int(y/2))
    if y%2 == 0 #even number
    	return 2*z
    else #odd number 
    	return 2*z + x

• n = y의 비트 수
• 시간복잡도: O(n)

---

3-2. Divide & Conquer 곱셈

• 곱셈 4번 필요
• 재귀 관계:

---

3-3. Karatsuba multiplication

• 곱셈을 3번으로 줄임: T(n) = 3T(n/2)+O(n) ⇒ Θ(n log⁡2 3) ≈ Θ(n^1.585)

---

재귀 관계 예제 풀이

예제 1

+) 예제 2, 예제 3 > kr 파일에 문제 및 해설 존재