, складових оператор, і для кожного оператора введення-виведення V b - середня кількість інформації h b , переданої при виконанні оператора .
3. Переходи між операторами Vi і Vj слід розглядати як випадкові події і характеризувати їх імовірностями Pij, тобто кожна дуга (i, j) графа алгоритму повинна бути відзначена ймовірністю переходу Pij, з якою перехід з вершини Vi виконується саме з цієї дузі, тобто до вершини Vj.
Так як обчислювальний процес не може припинятися у вершині Vi, то з імовірністю 1 відбудеться перехід до якої-небудь вершині графа алгоритму. З урахуванням цього ймовірності переходів повинні відповідати умові
, I = 0,1,2, ..., К-1
Значення Pij визначаються ймовірностями значень предикатами. Іншими словами, ймовірності Pij залежать від ймовірностей виконання умови, що перевіряється оператором i з метою вибору шляху переходу. Наприклад, нехай оператор 2 породжує перехід до оператора 3 при від'ємному значенні деякої змінної Х і до оператора 4 при Х Ві 0. Якщо відомо, що величина Х рівномірно розподілена в діапазоні (-1; +3), то з імовірністю 0,25 її знак негативний і з імовірністю 0,75 позитивний. З цього випливає, що перехід до оператора 3 відбувається з імовірністю Р2, 3 = 0,25 і перехід до оператора 4 - з імовірністю Р2, 4 = 0,75. Нехай далі оператор 7, замикає цикл, породжує перехід до оператора 1 в дев'яти випадках, а в одному випадку перехід відбувається в кінець алгоритму (цикл, що починається від оператора 1 і закінчується оператором 7, виконується 10 разів). Тоді вірогідність переходів Pi, 1 = 0,9 Pi, k = 0,1. Якщо за оператором i неодмінно виконується оператор j, то Pij = 1. Нехай П1, П2, ..., ПК-1 - середня кількість звернень до операторів V1, V2, ..., VK-1 за один прогін алгоритму. У такому випадку характеристики трудомісткості можуть бути обчислені таким чином:
- середнє число операцій, виконуваних при одному прогоні алгоритму
В
- середнє число звернень до файлу Fh
(h = 1,2, ..., H)
- середня кількість інформації, що передається при одному зверненні до файлу Fh
В
В останніх виразах підсумовування виконується по всіх вершин, що належать до класу основних операторів S0 або класу операторів введення-виведення Sh, що звертаються до файлу Fh.
Таким чином, для оцінки трудомісткості алгоритму необхідно визначити середнє число звернень n1, n2, ..., nk-1 до операторів. Припустимо, що ймовірності переходів Pkj постійні і після виконання оператора Vk (k = 1,2, ..., k-1) перехід до наступного оператору визначається ...
