• 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에 대한 함수)

 

 

 

'DataStructure' 카테고리의 다른 글

[자료구조] Lists  (0) 2022.04.17
[자료구조] Vector  (0) 2022.04.16
[자료구조] Queue  (0) 2022.04.09
[자료구조] Stacks  (0) 2022.04.08
[자료구조] Linked Lists  (0) 2022.04.08

+ Recent posts