Оценить трудоемкость алгоритма при: P12=0.3; P13=0.7; P24=0.5 ...

Сергей

Бесплатно Для оценки трудоемкости алгоритма нам необходимо составить систему алгебраических уравнений в соответствии с переходами на графе и общими правилами построения системы для данного случая.


Давайте назовем переменные T1, T2, T3, T4, T5, T6, T7, которые будут представлять среднее время обращения к каждому оператору.


Уравнения для операторов ввода-вывода:

Учитывая, что операторы ввода-вывода (K7 и K1) имеют фиксированную трудоемкость:


T7 = K7


T1 = K1


Уравнения для остальных операторов:

Для остальных операторов, среднее время обращения к ним будет зависеть от времени обращения к предыдущим операторам и вероятности перехода между ними.


Учитывая это, мы можем записать следующие уравнения:


T2 = P12 * T1 + P13 * T1


T3 = P24 * T2 + P25 * T2 + P35 * T1 + P37 * T1


T4 = P46 * T3 + P36 * T3


T5 = P56 * T3


T6 = P67 * T5


Вычисление трудоемкости алгоритма:

Трудоемкость алгоритма будет равна сумме трудоемкостей всех операторов.


Трудоемкость = K1 + K2 + K3 + K4 + K5 + K6 + K7


Решение системы уравнений:

Теперь мы можем решить полученную систему уравнений и найти среднее обращение к операторам алгоритма и его трудоемкость.


Вычислим значения T1, T2, T3, T4, T5, T6, T7, используя данные вероятности и трудоемкости операторов:


T1 = 100


T7 = 200


T2 = 0.3 * T1 + 0.7 * T1 = 0.3 * 100 + 0.7 * 100 = 100


T3 = 0.5 * T2 + 0.5 * T2 + 0.1 * T1 + 0.7 * T1 = 0.5 * 100 + 0.5 * 100 + 0.1 * 100 + 0.7 * 100 = 180


T4 = 1 * T3 + 0.2 * T3 = 1 * 180 + 0.2 * 180 = 216


T5 = 1 * T3 = 1 * 180 = 180


T6 = 1 * T5 = 1 * 180 = 180


Трудоемкость = K1 + K2 + K3 + K4 + K5 + K6 + K7 = 100 + 400 + 500 + 400 + 300 + 250 + 200 = 1950


Таким образом, среднее обращение к операторам алгоритма будет составлять:
T1 = 100
T2 = 100
T3 = 180
T4 = 216
T5 = 180
T6 = 180
T7 = 200


Трудоемкость алгоритма составляет 1950.