Виды и методы вычисления сложности алгоритма

 

 

 

] 1

 

СОДЕРЖАНИЕ

Введение.........................................................................................................    3

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

1.1. Определение алгоритма.........................................................................   5

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

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

2. Виды и методы вычисления сложности алгоритма.............................   15

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

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

Заключение...................................................................................................    24

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

 

 

 

 

 

ВВЕДЕНИЕ

Темой данной курсовой работы является сложность алгоритма, виды и методы его вычисления.

Цель курсовой работы - всестороннее рассмотрение проблем, связанных с означенной темой.

Для достижения поставленной цели в курсовой работе решаются следующие задачи:

1 .Исследование понятия сложности алгоритма.

2. Определение методов вычисления сложности алгоритма.

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

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

Двойственная задача минимизации емкостной сложности при ограничениях на временную сложность возникает реже в силу архитектурных особенностей современных ЭВМ, поскольку запоминающие устройства разных уровней, входящие в состав машины, построены так, что программе может быть доступна очень большая, практически неограниченная область памяти - виртуальная память. Недостаточное количество основной памяти приводит лишь к некоторому замедлению работы из-за обменов с диском. Так как в любой момент времени программа работает лишь с двумя-тремя значениями и использование кэша и аппаратного просмотра команд программы вперед позволяет заблаговременно перенести с диска в основную память нужные значения, то можно констатировать, что минимизация емкостной сложности не является первоочередной задачей.

 

 

 

 

 

 

 

 

 

 

1.ПОНЯТИЕ АЛГОРИТМА И ЕГО СЛОЖНОСТИ

1.1 .Определение алгоритма

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

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

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

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

В теории алгоритмов были введены различные формальные определения алгоритма и удивительным научным результатом является доказательство эквивалентности этих формальных определений в смысле их равномощности. Варианты словесного определения алгоритма принадлежат российским ученым А.Н. Колмогорову и А.А. Маркову.

Определение 1. (Колмогоров): Алгоритм - это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

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

Различные определения алгоритма, в явной или неявной форме, постулируют следующий ряд требований.

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

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

алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;

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

Другие формальные определения понятия алгоритма связаны с введением специальных математических конструкций (машина Поста, машина Тьюринга, рекурсивно-вычислимые функции Черча) и постулированием тезиса об эквивалентности такого формализма и понятия «алгоритм».

Будем рассматривать в дальнейшем, придерживаясь определений Поста, применимые к общей проблеме, правильные и финитные алгоритмы, т.е. алгоритмы, дающие 1-решение общей проблемы. В качестве формальной системы будем рассматривать абстрактную машину, включающую процессор с фон- Неймановской архитектурой, поддерживающий адресную память и набор «элементарных» операций соотнесенных с языком высокого уровня. В целях дальнейшего анализа примем следующие допущения:

каждая команда выполняется не более чем за фиксированное время;

-исходные данные алгоритма представляются машинными словами по

β битов каждое.

 

 

Конкретная проблема задается N словами памяти, таким образом, на входе алгоритма - Np = N*β бит информации. Программа, реализующая алгоритм для решения общей проблемы состоит из М машинных инструкций по βм битов - Мβ = М*β м бит информации. Кроме того, алгоритм может требовать следующих дополнительных ресурсов абстрактной машины:

Sd - память для хранения промежуточных результатов;

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

При решении конкретной проблемы, заданной N словами памяти алгоритм выполняет не более, чем конечное количество «элементарных» операций абстрактной машины в силу условия рассмотрения только финитных алгоритмов.¹

Определение 3 . Трудоёмкость алгоритма. Под трудоёмкостью алгоритма для данного конкретного входа - Fa(N), будем понимать количество «элементарных» операций совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе.

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

ψA=cl * Fa(N) + с2 * М + сЗ * Sd + с4 * Sr, где сі - веса ресурсов.

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

 

         

Пусть DA - множество конкретных проблем данной задачи, заданное в формальной системе. Пусть D є DA - задание конкретной проблемы и |D| = N.

В общем случае существует собственное подмножество множества DA, включающее все конкретные проблемы, имеющие мощность N:

обозначим это подмножество через DN: DN = {De DN,: |D| = NJ}

обозначим мощность множества DN через MDN , т.е. MDN = |DN |.

Тогда содержательно данный алгоритм, решая различные задачи размерности N, будет выполнять в каком-то случае наибольшее количество операций, а в каком-то случае наименьшее количество операций. Ведем следующие обозначения.

Fa˄(N) - худший случай - наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

Fa(N) = max {Fa (D)} - худший случай на DN

dϵd_n

Fa˅(N) - лучший случай - наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

Fa˅(N) = min {Fa (D)} - лучший случай на DN

dϵd_n

Fa(N) - средний случай - среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

Fa(N) = (1 / MDN)*X {Fa (D)} - средний случай на DN

dϵd_n

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

1.Количественно-зависимые по трудоемкости алгоритм. Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений:

Fa (D) = Fa (|D|) = Fa (N)

 

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

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

Fa (D) = Fa (dl,...,dn) = Fa (PI,... ,Pm), m < n

Примерами алгоритмов с параметрически-зависимой трудоемкостью являются алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов.

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

Fa (D) = Fa (||D||, Pl,...,Pm) = Fa (N, Pl,...,Pm)

Порядково-зависимые по трудоемкости алгоритмы. Среди разнообразия параметрически-зависимых алгоритмов выделим еще оду группу, для которой количество операций зависит от порядка расположения исходных объектов. Пусть множество D состоит из элементов (dl,...,dn), и

||D||=N,

Определим Dp = {(dl,...,dn)}-множество всех упорядоченных N-ок из dl,...,dn, отметим, что |Dp|=n!. Если Fa (iDp) ≠ Fa (jDp), где iDp, jDp є Dp, то алгоритм будем называть порядково-зависимым по трудоемкости.

Примерами таких алгоритмов могут служить ряд алгоритмов сортировки, алгоритмы поиска минимума и максимума в массиве.

 

 

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

Сложность алгоритма определяется вычислительными мощностями, необходимыми для его выполнения. Вычислительная сложность алгоритма часто измеряется двумя параметрами: Т (временная сложность) и S (пространственная сложность, или требования к памяти). И Т, и S обычно представляются в виде функций от п, где п - это размер входных данных. (Существую и другие способы измерения сложности: количество случайных бит, ширина канала связи, объем данных и т.п.)

Обычно вычислительная сложность алгоритма выражается с помощью нотации "О большого", т. е описывается порядком величины вычислительной сложности. Это просто член разложения функции сложности, быстрее всего растущий с ростом п, все члены низшего порядка игнорируются. Например, если временная сложность данного алгоритма равна 4п2+7п+12, то вычислительная сложность порядка п2, записываемая как 0(n2).

Временная сложность измеренная таким образом не зависит от реализации. Не нужно знать ни точное время выполнения различных инструкций, ни число битов, используемых для представления различных переменных, ни даже скорость процессора. Один компьютер может быть на 50 процентов быстрее другого, а у третьего шина данных может быть в два раза шире, но сложность алгоритма, оцененная по прядку величины, не изменится.¹ Это не жульничество, при работе с алгоритмами настолько сложными, как описанные в этой книге, всем прочим можно пренебречь (с точностью до постоянного множителя) в сравнении со сложностью по порядку величины.Эта нотация позволяет увидеть, как объем входных данных влияет на требования к времени и объему памяти. Например, если Т= О(n), то удвоение входных данных* удвоит и время выполнения алгоритма. Если Т=0(2n), то