Правила аналізу складності алгоритмів

У загальному випадку час виконання оператора або групи операторів можна розглядати як функцію з параметрами – розміром вхідних даних і/або одної чи декількох змінних. Але для часу виконання програми в цілому допустимим параметром може бути лише розмір вхідних даних.

Час виконання операторів присвоєння, читання і запису звичайно має порядок .

Час виконання послідовності операторів визначається за правилом сум. Тому міра росту часу виконання послідовності операторів без визначення констант пропорційності співпадає з найбільшим часом виконання оператора в даній послідовності.

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

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

ЛІТЕРАТУРА

1. Алферова. З.В. Теория алгоритмов.- М.: Статистика, 1973.- 164 с.

2. Вирт. Н Алгоритмы + структуры данных = программы.- М.: Мир, 1985.-406c.

3. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра, языки, программирование. — 3-е изд., перераб. и доп. — К.: Наук. думка, 1989. 14

4. Грин Д., Кнут Д. Математические методы анализа алгоритмов.- М.: Мир, 1987.- 120 с.

5. Грин Д., Кнут Д. Математические методы анализа алгоритмов.- М.: Мир, 1987.- 120 с.

6. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. — М.: Мир, 1981.

7. Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. – Омск: Диалог – Сибирь, 2003. – 108 с.

8. Дж. Макконелл. Анализ алгоритмов. Техносфера. Москва, 2002.

9. Игошин В.И., Математическая логика и теорія алгоритмов, М.:Изд.центр «Академия», 2008. – 448с.

10. Калужнін Л. А., Королюк В. С. Алгоритми і математичні машини. — К.: Вища шк., 1964.

11. Кнут Д. Искусство программирования. Т.1. Основные алгоритмы. 2000, Вильямс.

12. Кнут Д. Искусство программирования. Т.2. Получисленные алгоритмы. 2000, Вильямс.

13. Кнут Д. Искусство программирования. Т.3. Сортировка и поиск. 2000, Вильямс.

14. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ. М.: МЦНМО, 2000

15. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. — М.: Наука, 1975.

16. Лісовик Л.П., Шкільняк С.С. Теорія алгоритмів: Навч. посібник.- К.: Видавничий поліграфічний центр “Київський університет”, 2003.-163 с.

17. Мендельсон Э. Введение в математическую логику. — М.: Мир, 1976.

18. Минский М. Вычисления и автоматы. — М.: Мир, 1971.

19. Роберт Седжвик. Фундаментальные алгоритмы на JAVA. Части 1-4. Анализ, структуры данных, сортировка, поиск. DiaSoft. Москва, Санкт-Петербург, Киев, 2003.

20. Роберт Седжвик. Фундаментальные алгоритмы на С++. Часть 5. Алгоритмы на графах. DiaSoft. Москва, Санкт-Петербург, Киев, 2002.

21. Трахтенброт Б. А. Алгоритмы и вычислительные машины. — М.: Сов. радио, 1974.

22. Тьюринг А. Может ли машина мыслить? — М.: Физматгиз, 1960.

23. Шкільняк С.С. Математична логіка: приклади і задачі. – Київ: ВПЦ "Київський університет", 2002. – 56 с.

Підписано до друку 18.03.2014 р.

Формат 84х108\32. Папір офсетний Друк на різографі.

Умов.-друк.арк. 3,3. Обл..-вид. арк. 3,7. Зам. №5.

Тираж 100 прим.

Віддруковано у ТзОВ “Гал-друк”

м.Тернопіль, вул. Бродівська, 44

тел./факс 520563

Дата добавления: 2014-11-08; Просмотров: 757; Нарушение авторских прав?; Мы поможем в написании вашей работы!