lecture 6

• Online Algorithm

  • 전체 입력을 알지 못하고 그때그때 받아서 처리하는 방법

• Offline Algorithm

  • 전체 입력을 알고 있어서 한 번에 처리하는 방법
  • 전체 입력을 알고있으므로 문제해결책의 최적화가능!

• Competitive ratio 경쟁률

  • 온라인 알고리즘과 오프라인 알고리즘의 비율 = ratio on / ratio off

• 예시

전제 : 언젠간 산다 → 온라인 알고리즘에 의한 가격은 500 + 50(k-1)

오프라인 알고리즘에 의한 가격은 최적화 가능하므로, k가 10보다 큰지 작은지로 나눈다

→ 두 알고리즘의 비율 계산 = 경쟁률 = 1 + 9/k = 0.9 + k/10

• k = 10이 나오고 경쟁률 = 1.9가 나온다.

p 구매 비용, r 렌탈 비용 → 구매비용이 렌탈비용의 배수일때 경쟁률은 2-r/p가 된다!

• better-late-than-never : N일동안의 렌탈비용이 구매비용보다 더 비싼 시점을 의미함 (안사는거보다 늦더라도 사야된다!)

• LRU : Least - Recently - Used = 가장 덜 최근에 사용된 것부터 사용한다