Оценка сложности алгоритмов.

Оглавление

Введение 3

1. Алгоритм и его свойства 5

2. Модель RAM (Random Access Machine) 12

3. Сложность алгоритмов 13

3.1. Оценка сложности алгоритмов 13

3.2. Классификация алгоритмов по сложности 15

3.3. Теория сложности и примеры трудных задач 17

Заключение 22

Список литературы 24

Введение

Для любого программиста важно знать основы теории алгоритмов, так как именно эта наука изучает общие характеристики алгоритмов и формальные модели их представления. Ещё с уроков информатики учат составлять блок-схемы, что, в последствии, помогает при написании более сложных задач, чем в школе. Также не секрет, что практически всегда существует несколько способов решения той или иной задачи: одни предполагают затратить много времени, другие ресурсов, а третьи помогают лишь приближённо найти решение.

Всегда следует искать оптимум в соответствии с поставленной задачей, в частности, при разработке алгоритмов решения класса задач.

Важно также оценивать, как будет вести себя алгоритм при начальных значениях разного объёма и количества, какие ресурсы ему потребуются и сколько времени уйдёт на вывод конечного результата.

Алгоритм – это точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату.

При разработке алгоритмов очень важно иметь возможность оценить ресурсы, необходимые для проведения вычислений, результатом оценки является функция сложности (трудоемкости).

Оцениваемым ресурсом чаще всего является процессорное время (вычислительная сложность) и память (сложность алгоритма по памяти). Оценка позволяет предсказать время выполнения и сравнивать эффективность алгоритмов.

Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Цель работы – оценка сложности алгоритмов.

В рамках работы будут рассмотрены следующие вопросы:

1. Алгоритм и его свойства.

2. Модель RAM (Random Access Machine).

3. Сложность алгоритмов.

Работа состоит из введения, трех глав, заключения и списка литературы.