- •Матеріали для підготовки до держіспиту
- •Програмування
- •1. Об’єкти. Поняття об’єкту у процедурному та об’єктно-орієнтованому програмуванні
- •2. Загальні принципи і основні елементи об’єктно-орієнтованого програмування
- •3. Типи та класи у сучасній мові програмування. Взаємовідношення понять "клас" та "об’єкт"
- •4. Поліморфізм як одна з компонентів ідеології сучасного програмування
- •5. Принцип модульності у програмуванні. Процедури і функції, їх побудова та застосування
- •6. Динамічний розподіл ресурсів пам’яті при виконанні програми
- •7. Застосування шаблонів функцій та класів при створенні програм. Можливості параметризованих класів.
- •8. Успадкування та створення ієрархій класів. Проблеми, які вирішуються шляхом використання успадкування
- •9. Атрибути доступу як засіб підвищення надійності програмування
- •Теорія систем та математичне моделювання
- •10. Основні поняття теорії систем. Класифікація систем
- •11. Методи опису систем
- •12. Математичні та комп’ютерні моделі. Їх види та характеристики
- •13. Ідентифікація моделей і задача апроксимації. Методи апроксимації даних
- •14. Моделювання стаціонарних систем. Нелінійні системи
- •15. Моделювання динаміки систем. Системи з локалізованими та розподіленими властивостями.
- •Аналіз та побудова алгоритмів
- •16. Поняття алгоритму. Види алгоритмів, способи їх подання.
- •17. Оцінювання ефективності алгоритму. Функція складності.
- •18. Математичний аналіз і емпіричне дослідження алгоритмів.
- •19. Обчислювальна складність задач. Класи задач p та np.
- •20. Функція складності алгоритму та асимптотичні відношення.
17. Оцінювання ефективності алгоритму. Функція складності.
Рассмотрим некоторую задачу Р и алгоритм АР , который решает эту задачу. Для оценивания эффективности алгоритма Ар используют т.н. функции сложности: функцию временной сложности Ft(n) и функцию пространственной сложности Fs(n). Значением функции Ft(n) является время работы алгоритма, а функции Fs(n) - объем используемой памяти. Аргументом функции сложности в обоих случаях является размер входа алгоритма.
Для анализа алгоритмов важными являются следующие свойства функция сложности.
1 Функция F(n) является отображением вида F: AB, где A,B = [0, +] .
2. Функция F(n) является неубывающей при достаточно больших n: т.е. существует такое n0>0, что для любых n1, n2 > n0 и n1 > n2 имеет место F(n1) F(n2).
Далее под функцией сложности понимаем функцию временной сложности.
При выполнении анализа алгоритма значение функции сложности может быть представлено в относительных единицах.
Время работы алгоритма в большинстве случаев зависит не только от самого алгоритма, но также и от характера (или просто от значения) входных данных. В связи с этим различают а) наихудший случай, б) наилучший случай и в) среднее время работы алгоритма. Среднее понимается как среднее время на всем множестве вариантов входных данных.
Вариант б (наилучший случай) является наименее актуальным. В большинстве случае оценивается наихудший случай или среднее время. В зависимости от изучаемой задачи, наихудший случай может встречаться очень редко или, наоборот, довольно часто. Например, для задачи обработки запроса базой данных плохим запросом обычно является поиск элемента, который, в ней отсутствует. И такая ситуация реализуется довольно часто. В то же время существует немало задач, для которых характерна обратная ситуация, когда входные данные, соответствующие наихудшему случаю, встречаются редко. Примером такой задачи может служить задача поиска максимальной клики в графе.
Что же касается оценок эффективности работы алгоритма в среднем, то следует отметить следующее. Если время работы алгоритма зависит от значения входа, то время работы в среднем будет зависеть от функции распределения времени выполнения алгоритма на множестве входных значений и от распределения их вероятностей. При оценках времени работы в среднем обычно это распределение считают равномерным, хотя на практике оно может отличаться от равномерного.
В некоторых случаях время работы алгоритма в среднем может быть близким времени работы алгоритма в худшем случае. Например, для алгоритма Isertion-Sort функция времени работы и в худшем случае и в среднем является квадратичной.
В качестве меры эффективности алгоритма используют скорость роста его функции сложности с увеличением размера входа. Скорость роста функции F(n) является, с одной стороны, фундаментальной характеристикой алгоритма, а с другой, она отображает возможности его практического использования. В связи с этим, целью анализа алгоритма обычно является не установление точного вида функции сложности, а получение ее т. н. асимптотического класса, который позволяет судить о скорости роста функции сложности.