2.2.Оценка средней трудоемкости алгоритма методом марковских цепей

Этот метод предполагает постоянство P_ij, вероятностей переходов между вершинами, и независимость этих величин от того, каким образом процесс попал в вершину i.

Процесс реализации алгоритма в этом случае можно рассматривать как марковский процесс с К+1 состоянием, где состояние 1 является начальным, а состояние К - поглощающим.

При этом числа n₁,…,n_k можно рассматривать как средние числа пребывания марковского процесса в состояниях 1,..,К.

В соответствии с теорией марковских цепей, вычислять их можно как корни системы линейных уравнений:

k

n₁ = 1 - Σ P_ji*n_j

j=1

k (2)

n_i = Σ P_ji*n_j , i=1,…,k

j=1

Составим систему уравнений (2) для модели БСА из раздела 2.1. Решив их, найдем среднюю трудоемкость алгоритма по формуле (1).

Имеем:

n_iq_i

n₁=1 n₁=1 1

n₂=n₁+n₅+0,9n₇ n₂=25 50

n₃=0,5n₂ n₃=12,5 50

n₄=n₃+0,5n₂ n₄=25 50

n₅=0,6n₄ n₅=15 60

n₆=0,4n₄ n₆=10 60

n₇=n₆ n₇=10 20

n₈=0,1n₇ n₈=1 5

_ 8

q= å n_iq_i =296.

i=1

Предлагаю ознакомиться с аналогичными статьями: