тільки розподілом ймовірностей Pkj, тобто не залежить від ходу обчислювального процесу в минулому - до переходу до оператора Vk. При зазначених припущеннях процес виконання алгоритму є марковским процесом з К станами S1, S2, ..., Sk відповідними перебуванню процесу у вершинах V1, V2, ..., Vk алгоритму. Стану S1, S2, ..., Sk-1 - безнадійні (процес після якогось числа кроків неодмінно залишає їх), стан Sk - поглинає (досягнувши його, процес припиняється). Початковим є стан Si, певне дугою (0, i), що виходить з початкової вершини графа. Для спрощення позначень домовимося, що i = 1, тобто початковий стан - S1. Порядок зміни станів визначається графом алгоритму, дуги якого відзначені вірогідністю переходів Pij. Зазначений граф алгоритму можна розглядати як граф марковського ланцюга. p> Середнє число П1, П2, ..., ПK-1 перебування марковского процесу в неповоротних станах S1, S2, ..., Sk-1 визначається корінням системи лінійних алгебраїчних рівнянь ni = d1, i + (i = 1,2, ..., k -1), де d1, i - символ Кронекера d1, i =. Система цих рівнянь будується виходячи з таких міркувань. Значення ni дорівнюватиме, принаймні, одному, якщо процес починається від стану з номером i = 1, що зазначено символом d1, i. В інших випадках процес потрапляє в стан Si лише з інших станів j = 1,2, ..., k-1 з ймовірністю Pij. Якщо процес перебував у стані j nj раз і Pji В№ 0, то процес з цього стану потрапить у стан i в середньому Pijnj разів. Підсумовуванням значень Pijnj по всіх j знаходиться число влучень процесу в стан з усіх інших станів j. Значення П1, П2, ..., ПK-1 визначаються рішенням системи лінійних алгебраїчних рівнянь, канонічна запис якої має вигляд:
(p1 ,1-1) n1 + p2, 1n2 + ... + pk-1, 1nk-1 = - 1,2 n1 + (p2 ,2-1) n2 + ... + pk-1, 2nk-1 = 0
......................................., k-1n1 + p2, k-1n2 + ... + (pk-1, k-1-1) nk-1 = 0
Для прикладу визначимо трудомісткість алгоритму, заданого раніше наведеним графом. Для простоти приймемо, що всі оператори алгоритму - основні (оператори введення-виведення відсутні) і кількість операцій Ki, породжуваних кожним оператором, постійно і дорівнює 1. На основі графа і форми будуємо систему із семи лінійних алгебраїчних рівнянь:
-n1 +0,9 n2 =-1-n2 = 0
, 25n2-n3 = 0
, 75n2-n4 = 0
, 5n3 +0,2 n4-n5 = 0
0,8 n4-n6 = 0
, 5n3 + n5 + n6-n7 = 0
Вирішуючи систему, визначаємо середнє число влучень обчислювального процесу в стани S1, S2, ..., S7:
n1 = 10; n2 = 10; n3 = 2,5; n4 = 7,5; n5 = 2,75; n6 = 6; n7 = 10.
Підставляючи отримані значення, отримуємо оцінку трудомісткості алгоритму:
ni = 10 +10 +2,5 +7,5 +2,75 +6 +10 = 48,75
Розглянутий спосіб визначення трудомісткості алгоритмів є універсальним, дозволяючи отримувати оцінки для алгоритмів з будь-якою структурою, простий з точки зору програмування, але потребує вирішення системи алгебраїчних рівнянь зазвича...
