1.2. Моделі обчислень
Означення 1.3 Модель обчислень визначає набір допустимих елементарних операцій і вартості цих операцій.
Елементарні операції - це такі операції, для кожної із яких призначається фіксована вартість, хоча ця вартість неоднакова для різних елементарних операцій.
Основні моделі обчислень:
РАМ - машина з довільним доступом до пам'яті (або рівно доступна адресна машина );РАСП - машина з довільним доступом до пам'яті і програмою, яка зберігається (або рівно доступна адресна машина із програмою, яка зберігається); машина Тюрінга.
Модель РАМ (дійсна RAM - Random Access Machine) в кожній комірці пам'яті може зберігати єдине дійсне число та характеризується наступними елементарними операціями, що мають одиничну вартість:
- Арифметичні операції: +, -, *, /.
- Операції порівняння двох дійсних чисел: <,
, =, 
, 
, >.
- Непряма адресація пам'яті лише з цілочисельними адресами.
При необхідності використовуються логічні, алгебраїчні та тригонометричні операції.
Обчислювальна складність РАМ-програм.
Означення 1.4 Складність в гіршому випадку - це максимальна міра ефективності даного алгоритму для всіх задач даного розміру.
Означення 1.5 Якщо за міру складності береться "середня" складність за всіма входами даного розміру, то вона називається середньою складністю.
Часова складність в гіршому випадку РАМ програми - це функція f(n), рівна найбільшій (за всіма входами розміру n) із сум часів, витрачених на кожну спрацьовану команду.
Часова складність в середньому - це середнє, взяте по всім входам розміру n тих же самих сум.