Курсовая теория на тему Оценка сложности работы алгоритма программы

Содержание:

Введение 3
Глава 1. Основы работы алгоритма программы 5
1.1. Понятие алгоритма 5
1.2. Основные виды алгоритмов 11
Глава 2. Оценка сложности алгоритма 17
2.1. Понятие сложности алгоритмов 17
2.2. Основные методы и приемы анализа сложности 26
2.3. Сложность циклических и рекурсивных алгоритмов 31
Заключение 44
Список литературы 45

Введение:

Традиционно в программировании понятие сложности алгоритма связано с использованием компьютерных ресурсов: сколько процессорного времени требуется программе для ее выполнения и сколько она потребляет машинной памяти. Учет памяти обычно основан на объеме данных и не учитывает объем памяти, используемой для написания программных команд. Время вычисляется в относительных единицах, так что эта оценка, если это возможно, одинакова для машин с различными тактовыми частотами и с незначительными изменениями в архитектуре.
Алгоритмы имеют определенное начало, определенный конец и конечное число шагов. Алгоритм создает одну и ту же выходную информацию, учитывая ту же входную информацию, и несколько коротких алгоритмов могут быть объединены для выполнения сложных задач, таких как написание компьютерной программы.
Следовательно, алгоритм относится к набору правил или инструкций, которые шаг за шагом определяют, как должна выполняться работа для получения ожидаемых результатов.
Этот подход был разработан исторически и ориентирован в первую очередь на научные и инженерные приложения теории алгоритмов: объемы данных значительно превышают размер самой программы, и программа может работать в течение нескольких часов. В то время как в научных и инженерных приложениях большое количество вычислительного времени неудобно только для пользователей, в некоторых других областях ресурсы настолько критичны, что весь проект может оказаться непрактичным из-за неэффективной работы программы. Эти области включают в себя системы реального времени. Это компьютерные системы, которые управляют процессами в реальном мире или обрабатывают информацию, которая служит для принятия оперативных решений.
В данной работе будут подробно рассмотрены характеристики сложности алгоритмов.
Цель работы – рассмотреть оценку сложности работы алгоритма программы.
Задачи работы:
 изучить понятие алгоритма;
 рассмотреть основные виды алгоритмов ;
 изучить понятие сложности алгоритмов ;
 рассмотреть основные методы и приемы анализа сложности;
 рассмотреть сложность циклических и рекурсивных алгоритмов .

Заключение:

Под алгоритмом чаще всего понимают понятное и определенное предписание о выполнении в некоторой последовательности шагов (операций или действий) для поиска решения любой из задач, относящейся к определенному типу задач. Эта характеристика не является точным математическим определением, однако она достаточно ясно раскрывает сущность этого понятия и полностью совпадает с принятыми в математике толкованиями.
Оценка сложности – это отличный способ не только сравнить алгоритмы, но и предсказать время их выполнения. Никакие тесты производительности не дадут этой информации, потому что они зависят от характеристик конкретного компьютера и обрабатывают конкретные данные (не обязательно в худшем случае).
Анализ алгоритмов позволяет определить минимально возможную трудоемкость, например:
 алгоритм поиска элемента в неупорядоченном массиве не может иметь более высокий балл сложности, чем O (n). Это происходит потому, что невозможно определить отсутствие элемента в массиве (в худшем случае) без просмотра всех его элементов;
 можно формально доказать, что алгоритм сортировки произвольных массивов, работающий лучше, чем O(n logn), невозможен.
Нередко на собеседованиях вас просят разработать алгоритм с более высокой оценкой, чем это возможно. Сами задачи сводятся к стандартному алгоритму. Человек, не знакомый с асимптотическим анализом, начнет писать код, но вам нужно только обосновать невозможность такого алгоритма.

Фрагмент текста работы:

Глава 1. Основы работы алгоритма программы
1.1. Понятие алгоритма
Теория алгоритмов — молодая наука, появившаяся в конце ХХ века, содержит точное определение алгоритма, но она также рассматривает его интуитивное определение, которое называется «интуитивным понятием» алгоритма. Считается, что эта концепция сложилась за долгие годы существования человечества в результате его практического опыта [3].
Исторически термин «алгоритм» происходит от фамилии узбекского математика девятого века Мухаммада ибн Мусы аль-Хорезми, который первым сформулировал правила для четырех основных арифметических операций. Сначала эти правила назывались алгоритмами, но затем этот термин получил дальнейшее развитие преимущественно в математике – алгоритмом назывался любой метод вычисления, единый для определенного класса исходных данных, например, нахождение производной функции. Одной из важнейших задач обучения математике является овладение общими вычислительными алгоритмами. Другими словами, если ученика учат умножать два числа в столбик, то предполагается, что он овладевает не умножением конкретных выбранных чисел, а универсальным методом (алгоритмом), который впоследствии может быть использован для нахождения произведения любой пары конечных чисел. Таких примеров можно найти немало, и не только в математике – термин «алгоритм» стал широко использоваться [10].
Даже с развитием языка люди разработали правила поведения, заповеди, законы — самые простые алгоритмы — для совместной жизни в больших группах. Язык также является подходящим способом передачи процедур и навыков — более сложные алгоритмы. Первые профессии возникли из специализации отдельных членов группы на определенных навыках.