Зміст
Введення
. Поняття алгоритму і заходи його складності
. Тимчасова та емкостная складність алгоритмів
. Верхні і середні оцінки складності алгоритмів
. Основні методи і прийоми аналізу складності
. Аналіз складності рекурсивних алгоритмів
. Оптимізація алгоритмів
Висновок
Список використаної літератури
Введення
Традиційно в програмуванні поняття складності алгоритму пов'язано з використанням ресурсів комп'ютера: наскільки багато процесорного часу вимагає програма для свого виконання, наскільки багато при цьому витрачається пам'ять машини? Облік пам'яті зазвичай ведеться за обсягом даних і не береться до уваги пам'ять, витрачається для запису команд програми. Час розраховується у відносних одиницях так, щоб ця оцінка, по можливості, була однаковою для машин з різною тактовою частотою і з незначними варіаціями в архітектурі. p align="justify"> Такий підхід склався історично і орієнтується насамперед на наукові та інженерні програми теорії алгоритмів: обсяги даних значно перевищують розміри самої програми, а програма може виконуватися кілька годин. Якщо в наукових та інженерних додатках великий час обчислень доставляє лише незручність користувачам, то в ряді інших областей ресурси настільки критичні, що може виникнути проблема доцільності всього проекту через неефективну роботу програми. До таких областей відносяться системи реального часу (real-time systems). Це засновані на комп'ютерах системи, які управляють процесами в реальному світі або обробляють інформацію, що служить для прийняття оперативних рішень. p align="justify"> У даній роботі будуть детально розглянуті дві характеристики складності алгоритмів - тимчасова і емкостная. Але не будемо обговорювати складність (довжину) тексту алгоритму, оскільки вона більше характеризує виконавця (машину), його мова, а не метод вирішення задачі. Не будемо також обговорювати логічну складність розробки алгоритму - скільки людино-місяців потрібно витратити на створення програми, оскільки не представляється можливим дати об'єктивні кількісні характеристики. Обидві ці теми відносяться до області комп'ютерних наук, званої "технологія програмування" (software engineering). br/>
1. Поняття алгоритму і заходи його складності
У всіх сферах своєї діяльності, і зокрема в сфері обробки інформації, людина стикається з різними способами або методиками вирішення завдань. Деякі додаткові вимоги призводять до неформального визначення алгоритму:
Визначення 1.1: Алгоритм - це заданий на деякій мові кінцеве припис, що задає кінцеву послідовність здійсненних елементарних операцій для вирішення завдання, загальне для класу можливих вихідних даних.
Нехай D - область (безліч) вихідних даних завдання, а R - безліч мож...
