Лекція 3

§ 3.1. Обчислювальна складність рам-програм.

Важливими мірами складності алгоритму є часова й ємнісна складність, які розглядаються як функції розміру входу. Якщо при заданому розмірі в значенні міри складності береться найбільша її складність (по всіх входах цього розміру), то вона називається складністю в найгіршому випадку. Якщо ж в значенні міри складності береться “середня“ складність по всім входам даного розміру, то вона називається середньою складністю. Зазвичай середню складність знайти важче, ніж складність в найгіршому випадку. Потрібно ще прийняти деяке припущення про розподіл входів, а реальні допуски часто буває складно сформулювати математично. Будемо приділяти основну увагу найгіршому випадку, оскільки його простіше досліджувати і він має універсальну застосовність. Проте слід пам’ятати, що алгоритм з найменшою складністю в гіршому випадку не обов’язково має кращу складність в середньому.

Часова складність в найгіршому випадку ( або просто часова складність) РАМ-програми це функція рівна найбільшій ( по всім входам розміру n) із сум часів, затрачених на кожну спрацьовану команду, Часова складність в середньому – це середнє, взяте по всім входам розміру n, тих же самих сум. Такі ж поняття визначаються для ємкості пам’яті, тільки замість “часів, затрачених на кожну спрацьовану команду“ потрібно підставити “ємність всіх регістрів, до яких було звернення“.

Щоб точно визначити часову й ємнісну складності, потрібно указати час, необхідний для виконання кожної РАМ-команди, і обсяг пам’яті, який використовується кожним регістром. Розглянемо два таких вісових критерії.

При рівномірному ваговому критерію кожна РАМ-команда витрачає одну одиницю часу і кожен регістр використовує одну одиницю пам’яті. Якщо не зазначено інше, то складність РАМ-програм буде вимірюватися у відповідності з рівномірним ваговим критерієм.

Друге визначення, іноді більш реалістичне, приймає до уваги обмеженість розміру реальної комірки пам’яті й називається логарифмічним ваговим критерієм. Нехай l(i ) – логарифмічна функція на цілих числах, задана рівностями

Таблиця 3.1 дає логарифмічні ваги для всіх трьох можливих видів операнда а. В таблиці 3.2 наведені ваги РАМ-команд.

Таблиця 3.1 Логарифмічні ваги операндів

Операнд а	Вага
= і
І
і

Тут враховано, що для подання цілого числа n в регістрі треба бітів.

Логарифмічний ваговий критерій заснований на грубому припущені, що ціна виконання команди (її вага) пропорційна довжині її операндів. Наприклад, розглянемо вагу команди ADD . Спочатку ми повинні визначити складність декодування операнда, поданого адресом. Огляд цілого числа і вимагає часу l(i). Потім, щоб прочитати вміст c(i) регістра і й визначити його місцезнаходження, потрібен час l(c(i)). І, на кінець, зчитування вмісту c(i) вимагає часу l(c(c(i))). Оскільки команда ADD додає ціле число c(c(i)) до цілого числа c(0) в суматорі, то зрозуміло, що розумною вагою, котру слід надати команді ADD є

l(c(0))+ l(i)+ l(c(i))+ l(c(c(i))).

Таблиця 3.2

Логарифмічні ваги команд РАМ, де t(a) – вага операнда a, а b означає мітку

Команда	Вага
1.LOAD а 2..STORE і STORE 3. ADD а 4. SUB а 5. MULT а 6. DIV а 7. READ і READ 8. WRITE a 9. JUMP b 10. JGTZ b 11. JZERO b 12. HALT	1. t(a) 2. l(c(0)) + l(i) l(c(0)) + l(i) + l(c(i)) 3. l(c(0)) + t(a) 4. l(c(0)) + t(a) 5. l(c(0)) + t(a) 6. l(c(0)) + t(a) 7. l(вхід) + l(i) l(вхід) + l(i) + l(c(i)) 8. t( a) 9. 1 10. l(c(0)) 11. l(c(0)) 12. 1

Визначимо логарифмічну ємнісну складність РАМ-програм як суму по всіх регістрах, які працювали, включаючи суматор, величин , де – найбільше за абсолютною величиною число, котре знаходилося в і-тому регістрі за увесь час обчислення. Зрозуміло, що дана програма може мати радикально відмінні часові складності в залежності від того, який використовується ваговий критерій – рівномірний чи логарифмічний. Якщо розумно вважати, що кожне число, котре зустрічається в задачі, можна зберігати у вигляді одного машинного слова, то придатна рівномірна вагова функція. В іншій ситуації для реалістичного аналізу складності більш придатною може виявитися логарифмічна вага.