[자료구조] 알고리즘 분석

• Running Time:
  • 알고리즘: 입력 개체를 출력 개체로 전환시키는 일
  • Running Time은 일반적으로 입력 크기(n)에 정비례한다.
  • 컴퓨터 공학에서는 가장 오래 걸리는 경우(Worst Case)를 분석한다.
    • 분석이 쉽다.
    • 게임, 금융, 로봇 등의 분야에서 Worst Case가 매우 중요하다.
  • 시행적 분석(Experimental Studies)
    • 알고리즘을 직접 짜서 프로그램을 돌려 시간을 재는 함수등을 이용해 Running Time을 재는 방법
    • 알고리즘을 직접 짜는 것이 중요하며, 개발자의 실력차에 따라 차이가 발생한다.
    • 실험에 포함되지 않은 입력값이 존재할 수 있다.
    • 두 알고리즘을 비교할 때, 동일한 하드웨어와 소프트웨어 사용이 필수적이다.
  • 점근적 분석(Theoretical Analysis)
    • 고급 서술로 실행하지 않고도 분석이 가능하다.
    • 입력크기(n)에 대한 함수로 Running Time을 표현할 수 있다.
    • 하드웨어와 소프트웨어 환경을 무시하고 분석할 수 있다.
    • n이 충분히 커지는 경우를 대비한다.
  • 의사코드(PseudoCode)
    • 알고리즘을 서술하기 위한 고급 서술 방법
    • 산문보다 구조적이다.
    • 프로그램보다 대략적이며 세부적인 부분은 표현하지 않는다.
    • 의사코드 사용법
      • 제어문
        • if_(condition)_then_(action)_[else_]
        • while_(condition)_do_(action)_
        • repeat_(action)_until_(condition)_
        • for_(condition)_do_(action)
        • 중괄호 대신 들여쓰기를 사용함
      • 함수표현

                                    Algorithm method (arg[,arg...])

                                       Input ~

                                      Output ~

• • • • 표현
        • <- 할당(C++에서의 =)
        • =  동일(C++에서의 ==)
        • 제곱과 같은 수학적 표기법 가능

• • 의사코드를 활용한 점근석 분석
    1. 알고리즘을 의사코드로 서술한다.
    2. Primitive Operation들의 수를 집계한다.
    3. 알고리즘의 Running Time을 Input size(n)에 관한 함수로 표현한다.
    4. 알고리즘 Running Time에 대한 함수를 Big-O표기법으로 표현한다.
  • Random Access Machine (RAM) 
    • 무제한의 메모리를 가진 가상의 Cpu
    • 이 가상의 기계는 메모리가 무한하며, 임의의 메모리셀에 넘버링이 되어있다.
  • Primitive 연산 : 알고리즘에서 수행되는 연산중 기본 연산
    
    • 의사코드를 보고 알 수 있음
    • 프로그래밍 언어에서 구애 받지 않고 사용가능
    • RAM 모델에서는 Input size(n)에 관계없이 일정한 수행시간(상수시간)이 걸린다
    • 종류
      • 사칙 연산
      • 변수에 값 할당
      • 배열에서 임의의 index에 접근
      • 함수호출
      • 함수의 return
    • Primitive 연산 Count
      
      1. 의사코드 조사
      2. Primitive operation의 최대 개수 결정
      3. Input size(n)에 대한 함수로 결정 

Algorithm arrayMax(A,n)         current <- A[0]    할당 한 번, 접근 한 번  ->   2                 *for i  <-  1 to n-1   do   -> 3n                       if A[i] > currentMax then   인덱스에 접근 한 번 비교연산 한 번 n-1 반복 -> 2(n-1)                                  currentMax = A[i]   인덱스에 접근 한 번, 할당 한 번 n-1반복 ->2(n-1)         return currentMax      한 번 -> 1                                                          -> 총 연산 수 : 7n-1

   *      

//i=1~n -> i=n이되어야 for문 탈출 -> i는 n까지 증가 -> 증가연산 n번
for (i=1   ;i<=n-1    ;i++)
//   1번    비교연산 n번  n-1번 증가         
//         n-1연산 n번 
//연산 수는 3n

• Running Time 추정

알고리즘 arrayMax의 worst case일때 primitive operation 연산 수는 7n - 1 primitive 연산이 가장 빠른 경우의 시간 = a primitive 연산이 가장 느린 경우의 시간 = b arrayMax의  worst case 시간 = T(n)  a(7n-1) <= T(n) <= b(7n-1) ∴ T(n)은 두 선형 함수 사이에 있다.

* a, b 는 컴퓨터의 하드웨어와 소프트웨어의 성능에 대해 영향을 받을 수 있다.

** 다만 n에관한 함수 T(n)에는 영향을 주지않는다. -> 차수가 바뀌진 않음

• n에관한 함수를 이용한 Running Time 추정
  
  • n이 충분히 커지면 함수의 값 보다는 함수의 증가율이 유의미 (극한개념)
  • 함수의 증가율로서 측정
  • 최고 차항이 아닌 항은 함수의 증가율에 영향을 미치지 않음
  • n이 충분히 커지면 계수는 증가율에 영향을 미치지 않는다
  • 중요한 건 최고차항의 차수
• Big-Oh notation
  • O(g(n)) : f(n) <= c*g(n) 을 만족하는 함수들의 집합 
  • (n>= n0, n0는 자연수), (c는 양의 실수, f(n),g(n)은 n에 대한 함수)
  • "Big-Oh of g(n)" or "Oh of g(n)"

예시 -7n - 1 은 O(n)   c = 7 , n0 = 1 -3n^3 + 20n^2 + 5 은 O(n^3)   c = 4 ,n0 = 21 일반적으로 g(n),c,n0은 최솟값으로 표기

• Big-Oh 표기 법
  • g(n)은 가장 낮은 차수로 표현
  • g(n)은 계수가 1인 단항식으로 표현  (ex. n, n^2, n^3, log(n), 2^n)

 

• Big-Omega : 증가율이 작은 함수들의 집합 (증가율의 하한) 
  • Omega(g(n)) : f(n) >= c*g(n) 을 만족하는 함수들의 집합 
  • (n>= n0, n0는 자연수), (c는 양의 실수, f(n),g(n)은 n에 대한 함수)
• Bif-Theta : 증가율이 같은 함수들의 집합
  • Theta(g(n)) :  c'*g(n) <= f(n) <= c"*g(n) 을 만족하는 함수들의 집합 
  • (n>= n0, n0는 자연수), (c'과 c" 는 양의 실수, f(n),g(n)은 n에 대한 함수)