Читать реферат по всему другому: "Оценка сложности алгоритмов" Страница 1

(Назад) (Cкачать работу)

Содержание

Введение

. Понятие алгоритма и меры его сложности

. Временная и емкостная сложность алгоритмов

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

. Основные методы и приемы анализа сложности

. Анализ сложности рекурсивных алгоритмов

. Оптимизация алгоритмов

Заключение

Список использованной литературы

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

Такой подход сложился исторически и ориентируется прежде всего на научные и инженерные приложения теории алгоритмов: объемы данных значительно превышают размеры самой программы, а программа может выполняться несколько часов. Если в научных и инженерных приложениях большое время вычислений доставляет лишь неудобство пользователям, то в ряде других областей ресурсы настолько критичны, что может возникнуть проблема целесообразности всего проекта из-за неэффективной работы программы. К таким областям относятся системы реального времени (real-time systems). Это основанные на компьютерах системы, которые управляют процессами в реальном мире или обрабатывают информацию, служащую для принятия оперативных решений.

В данной работе будут подробно рассмотрены две характеристики сложности алгоритмов - временная и емкостная. Но не будем обсуждать сложность (длину) текста алгоритма, поскольку она больше характеризует исполнителя (машину), его язык, а не метод решения задачи. Не будем также обсуждать логическую сложность разработки алгоритма - сколько человеко-месяцев нужно потратить на создание программы, поскольку не представляется возможным дать объективные количественные характеристики. Обе эти темы относятся к области компьютерных наук, называемой "технология программирования" (software engineering).

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

Определение 1.1: Алгоритм - это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных.

Пусть D - область (множество) исходных данных задачи, а R - множество возможных результатов, тогда мы можем говорить, что алгоритм осуществляет отображение D → R. Поскольку такое отображение может быть не полным, то вводятся следующие понятия:

Алгоритм называется частичным алгоритмом, если мы получаем результат только для некоторых d є D и полным алгоритмом, если алгоритм получает правильный результат для всех d є D.

В теории алгоритмов были введены различные формальные определения алгоритма и удивительным научным

Похожие работы