Computational Complexity

• 알고리즘의 cost = operation cost의 합

• model의 computation(계산)에 명시되어 있는 것

  • 알고리즘이 사용할 수 있는 operation이 무엇이 있는지
  • 각 operation의 cost(time, space)

• 실행 비용(Execution costs)

  • 시간복잡도(cost complexity): 알고리즘을 푸는 데 걸리는 시간
  • 공간복잡도(space complexity): 알고리즘에 필요한 메모리 용량

시간복잡도 계산

• client program(ex. time module)을 사용하여 실행시간을 초 단위로 측정하는 방법
  (+) 측정이 쉬움
  (+) 실제 시간을 제공함
  (-) 측정하는 데 많은 시간이 필요함
  (-) 결과는 많은 요인(machine, compiler, data 등)에 따라 달라짐

• input size(N)으로 operation의 수를 계산하는 방법
  (+) machine에 관계없음 (==독립적)
  (+) 알고리즘의 확장성(scalability)을 제공함
  (-) 계산하기 지루함..(tedious)
  (-) 실제시간을 제공하지 않음

=> 우리는 asymptotic(=approximate)에만 관심이 있음!

Big O Notation

f(N)보다 함수 T(N)의 성장 순서가 작거나 같으면, 이를 T(N) ∈ O(f(N))이라고 씀
=> 시간복잡도의 simplification을 위함(formally, simply..)

• 1. 최악의 성능에 관심 갖기
• 2. 가장 높은 차수(highest order)(==more expensive)를 가진 operation에 집중하기
• 3. 하위의 항(lower order term)을 제거하기
• 4. 상수(constant) 제거하기
• 5. the tightest order

Asymptotic Analysis(점근적 분석)에서 제일 중요한 것은?

nⁿ, 2ⁿ순으로 제일 느리고 log2n이 제일 빠름