Оцінювання дисперсії трудомісткості алгоритмів

Для забезпечення необхідної точності розв‘язку деяких задач аналізу обчислювальних систем необхідні відомості про дисперсію трудомісткості алгоритму. По визначенню дисперсією (розсіюванням) дискретної випадкової величини називають математичне чекання квадрата відхилення випадкової величини від її математичного чекання [3]

, (1)

де x — дискретна випадкова величина; M(x) — математичне чекання величини x.

Дисперсія характеризує ступінь розкиду значень випадкової величини відносно свого середнього значення та чим більша дисперсія, тим більший розкид значень. Дисперсія має розмірність, що дорівнює квадрату розмірності випадкової величини. Коли бажано, щоб оцінка розсіювання мала розмірність випадкової величини, обчислюють середнє квадратичне відхилення, а не дисперсію.

Середнім квадратичним відхиленням випадкової величини x називають квадратний корінь з дисперсії, тобто:

. (2)

Процедура визначення дисперсії трудомісткості складна. В даній роботі розглядається формальна сторона цього питання [1].

Для обчислення дисперсії алгоритм представляється як марковський ланцюг з матрицею імовірностей переходів [2]

Тут K — кiлькiсть операторів алгоритму та елементи визначають імовірності переходу з станів у стани . Наприклад, алгоритм рис.1 відповідає матриці імовірностей переходів:

Рис. 1

Трудомісткість операторів представимо вектор-стовпцем:

.

Для визначення дисперсії необхідно обчислити квадратну матрицю

, (3)

де

— одинична матриця; - поелементна різниця матриць та , що представляє собою матрицю K-го порядку:

.

Обертанням матриці формується матриця , елементи якої мають зміст середнього числа попадань процесу у стани з номерами , якщо процес починається зі станів з номерами .

Таким чином, якщо алгоритм починає виконуватись від оператора з номером i=1, то кiлькiсть звертань до операторів задається першим рядком матриці . Помноживши матрицю на вектор-стовпець , отримаємо вектор-стовпець

, (4)

елементи якого визначають середню трудомісткість алгоритму, ініційованого від операторів відповідно.

Значення дисперсії можна визначити наступним матричним виразом:

(5)

Тут - діагональна матриця,

,

що одержується з елементів вектора L; - вектор-стовпці виду

,

,

що визначаються шляхом зведення у квадрат елементів векторів L та .

Елементи вектор-стовпця

визначають дисперсію часу виконання програми, що починається від операторів з номерами відповідно. Якщо алгоритм виконується завжди з першого оператора, то дисперсія задається першим елементом D₁ вектора D.

2. Приклад оцінювання дисперсії трудомісткості алгоритму

Нехай потрібно обчислити дисперсію трудомісткості алгоритму (рис.2).

Трудомісткість операторів складає та операцій.

Згідно з графом (рис. 2) будуємо матрицю імовірностей переходів:

.

Обчислюємо матрицю N:

.

Рис. 2 Граф алгоритму

Визначаємо вектор середньої трудомісткості алгоритму:

.

Перший елемент вектора визначає середню трудомісткість алгоритму, ініційованого від оператора 1, елемент - трудомісткість алгоритму, ініційованого від оператора 2, і т.ін.

Застосовуючи (5), знаходимо

Cередньоквадратичне відхилення трудомісткості алгоритму, ініційованого від першого оператора, становить .