알고리즘 평가방법

결정적 모델링, 큐잉 모델, Little's Fomula, Simulations

 

 

결정적 모델링

• 상황결정 후 상황을 이용해서 방법 A, B ,C 에 대한 waiting average 값들을 계산
• 단점 : 상황이 변하는데 한 상황가지고 어떤 알고리즘에도 좋다 이야기하기 어렵다.
• 수학적분석은 더 어려움

 

 

큐잉 모델

• 시스템에 여러가지 큐 작업들이 큐에 들어와서 다른 큐로 갔다가 또 다른 큐로 갔다가 움직이는 상황의 큐 네트워크 있고 작업들이 큐에 들어와서 큐 사이 움직이는 모델
• 가정하기를 큐에 들어오는 속도 , 큐에 들어오는 작업 확률 분포가 있다.
• 전체에서 기다리는 것 몇개인지, 평균시간이 얼마나 걸리는지 하는 것들을 계산해 낼 수 있다.
• 작업 도착 순서, 대기 시간에 대한 확률 분포들을 가정하고 난 다음 큐잉 시스템에서 기다리는 시간, 평균 큐의길이 이런 것들을 계산하는 모델을 큐잉 모델이라고 한다.

 

Little's Fomula

• 대기하고 있는 숫자 (n)
• 제일 뒤에서 앞까지 오는데 걸리는 시간 (w)
• 큐에 도착하고 있는데 시간당 몇개 (λ)
• 평균 대기 큐의 길이 n = wλ
• 큐잉 모델 분석
  • 평균 대기 시간, 도착률 알면 큐의 평균 길이 알게 된다.

 

 

Simulations 모의실험

• clock 이용 → 일정 시간 지나면 어떤 사건 일어날 수록 (프로세스 생성되고 죽고 몇초가 지나면 프로세스 끝나고 모델링 하기 위해 clock 사용)
• 프로그램 이용해서 모의 실험
• 분포에 따르는 데이터 가지고 실험 (데이터를 어떻게 구현하냐 문제)