[Chapter 1] Algorithm: Efficiency, Analysis, and Order

경희대학교 한치근 교수님 알고리즘 수업을 바탕으로 작성되었습니다.

 

알고리즘 (Algorithm)

 

• 페르시아의 수학자 이름 'al Khowarizmi' 로부터 유래된 단어
• 정의: 문제를 잘 해결할 수 있는 well defined 그리고 finite 한 시간 내에 종료되는 computational procedure

 

Algorithm vs Method

 

• Algorithm: Ends in a finite time manner
• Method: Don't know if it ends in finite time

---

알고리즘의 분석 (Analysis)

• 공간복잡도 (Memory complexity)
• 시간복잡도 (Time complexity) - 더 중요하게 생각
• 분석 방법의 종류
  • 모든 경우 분석 (Every-case Analysis)
    • 입력 크기에만 종속, 결과 값은 항상 일정
  • 최악의 경우 분석 (Worst-case Analysis) - 제일 중요함, 비관적 시각으로 알고리즘 고안
    • 입력 크기와 입력 값 모두에 종속
    • 단위 연산이 수행되는 횟수가 최대인 경우
  • 평균의 경우 분석 (Average-case Analysis)
    • 입력 크기에 종속
    • 모든 입력에 대하여 단위연산이 수행되는 기대치
  • 최선의 경우 분석 (Best-case Analysis)
    • 단위 연산이 수행되는 횟수가 최소인 경우 선택
• 차수 (Order): 높은 차수항이 궁극적으로 지배한다.
• 복잡도 함수 표기법
  • Big oh - $O( )$: 점근적 상한 (Asymptotic upperbound)
    • $O(f(n))$: 어떤 $c(f(n))$ 보단 궁극적으로 좋음
  • Small oh - $o( )$: 
  • Omega - $\Omega( )$
  • Small omega - $\omega( )$
  • Theta - $\Theta( )$

---

Alg 1.1 - 순차검색 (Sequential Search)

def Sequential_Search(lst, x):
    n = len(lst)
    for i in range(n):
        if x == lst[i]:
            return i+1

    return 0

• 시간복잡도 분석
  • 최악: $W(n)=n$
  • 평균
    1. $x$ 가 배열 $S$ 안에 있는 경우: $A(n)=\frac{n+1}{2}$
    2. $x$ 가 배열 $S$ 안에 있을 확률이 $p$인 경우: $A(n)=n(1-\frac{p}{2})+\frac{p}{2}$
  • 최선: $B(n)=1$

 

Alg 1.2 - 배열의 수 더하기 (Sum)

TBA

 

• 시간복잡도 분석
  • 덧셈: $T(n)=n$
  • 지정문: $T(n)=n+n+1$

 

Alg 1.3 - 교환정렬 (Exchange Sort)

def Exchange_Sort(lst):
    n = len(lst)
    for i in range(n-1):
    	for j in range(i+1,n):
            if lst[j] < lst[i]:
                s[j], s[i] = s[i], s[j]
    return lst

• 시간복잡도 분석
  • j loop: $T(n)=(n-1)+(n-2)+∙∙∙+1= \frac{(n-1)n}{2}$
  • 교환 연산: $T(n)=\frac{(n-1)n}{2}$

 

Alg 1.4 - 행렬 곱셈 (Matrix Multiplication)

TBA

• 시간복잡도 분석
  • for loop: $T(n)=n^3$

 

Alg 1.5 - 이분검색 (Binary Search)

TBA

 

순차검색 vs 이분검색

 

Alg 1.6 - 피보나치 수 구하기 - 재귀적 (Fib)

def fib(n):
    if n <=1:
        return n
    else:
        return fib(n-1)+fib(n-2)
    
print(fib(7))

같은 피보나치 수를 중복하여 계산하기 때문에 효율이 떨어짐

 

Alg 1.6 - 피보나치 수 구하기 - 반복적 (Fib2)

def fib2(n):
    f = []
    f.append(1)
    if n>0:
        f.append(1)
        for i in range(2,n):
            f.append(f[i-1]+f[i-2])
    return f[n-1]

 

피보나치 재귀적 vs 반복적

 

재귀법 → 분할정복법

반복법 → 동적계획법