Анализ эффективности алгоритмов

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ  ИНСТИТУТ

1. Кафедра прикладной информатики

 

 

КУРСОВАЯ РАБОТА

 

по дисциплине «Теоретические основы информатики»

 

 

на тему

«Анализ эффективности алгоритмов»

 

Вариант № 11

 

 

 

 

2. Исполнитель:

3. Шнейдер Яков Александрович

«Бизнес - информатика»

Курс 1

Группа: вечерняя

№ зачетной книжки: 11улд12311

 

Руководитель:

Никифорова С.В.

 

 

 

 

Владимир

2012 

 

Содержание

Введение 3

Теоретическая часть 4

1. Измерение эффективности алгоритмов 4
2. О-сложность алгоритмов 7

Практическая часть 14

Задание 1 14

Задание 2 16

Задание 3 20

Задание 4 21

Заключение 25

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Цель исследования: Выявить и систематизировать материалы по теме: «Анализ эффективности алгоритмов».

Задачи Исследования:

• Изучить литературу по теме исследования;
• Систематизировать теоретический материал;
• Выполнить практическую часть, состоящую их 4-х заданий.

    Задание 1. Расчет информационной емкости документов предметной          области.

    Задание 2. Построение инфологических моделей предметной области.

     Задание 3. Формирование информационных запросов к реляционной базе данных с помощью операций реляционной алгебры.

     Задание 4. Применение методов поиска и сортировки данных.

 

 

 

 

 

 

 

 

 

 

 

 

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Измерение эффективности  алгоритмов

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

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

Выбирая алгоритм, оцените  его эффективность.

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

Сравнение эффективности  алгоритмов должно быть сосредоточено  на их существенных различиях.

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

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

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

Три недостатка подхода, основанного на сравнении  программ

1. Как запрограммированы  алгоритмы?

Допустим, алгоритм А1 выполняется  быстрее, чем алгоритм А2. Это может  быть связано с тем, что программа, реализующая алгоритм ai, просто лучше  написана. Следовательно, сравнивая время выполнения программ, мы на самом деле сравниваем реализации алгоритмов, а не сами алгоритмы. Реализации алгоритмов сравнивать бессмысленно, поскольку они очень сильно зависят от стиля программирования и не позволяют определить, какой из алгоритмов эффективнее.

2. На каком компьютере  должны выполняться программы?

Особенности конкретного  компьютера также не позволяют сравнить эффективность алгоритмов. Один компьютер  может работать намного быстрее  другого, поэтому для выполнения программ необходимо применять один и тот же компьютер. Какой компьютер выбрать? Конкретные операции, составляющие основу алгоритма А1 на одном из компьютеров могут выполняться быстрее, чем операции алгоритма А2, а на другом компьютере - наоборот. Сравнение эффективности алгоритмов не должно зависеть от особенностей конкретного компьютера.

3. Какие данные вводятся  в программы?

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

Анализ алгоритма не должен зависеть от конкретных реализаций, компьютеров и данных.

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

Основной способ оценки эффективности алгоритма - подсчет  его операций.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

O-сложность алгоритмов

O(1) 
Большинство операций в программе выполняются только раз или только несколько раз. Алгоритмами константной сложности. Любой алгоритм, всегда требующий независимо от размера данных одного и того же времени, имеет константную сложность.

О(N) 
Время работы программы линейно обычно когда каждый элемент входных данных требуется обработать лишь линейное число раз.

О(N2), О(N3), О(Nа) 
Полиномиальная сложность. О(N2)-квадратичная сложность, О(N3)- кубическая сложность

О(Log(N)) 
Когда время работы программы логарифмическое, программа начинает работать намного медленнее с увеличением N. Такое время работы встречается обычно в программах, которые делят большую проблему в маленькие и решают их по отдельности.

O(N*log( N)) 
Такое время работы имеют те алгоритмы, которые делят большую проблему в маленькие, а затем, решив их, соединяют их решения.

O(2N) 
Экспоненциальная сложность. Такие алгоритмы чаще всего возникают в результате подхода именуемого метод грубой силы.

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

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

Определение сложности  алгоритма в основном сводится к анализу циклов и рекурсивных вызовов.

Например, рассмотрим алгоритм обработки элементов массива. 
For i:=1 to N do 
Begin 
... 
End;

Сложность этого алгоритма O(N), т.к. тело цикла выполняется N раз, и сложность тела цикла равна O(1).

Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью. 
For i:=1 to N do 
For j:=1 to N do  
Begin 
... 
End; 
Сложность этой программы О(N2).

Давайте оценим сложность  программы "Тройки Пифагора"

Существуют два способа  анализа сложности алгоритма: восходящий (от внутренних управляющих структур к внешним) и нисходящий (от внешних  и внутренним).

O(H)=O(1)+O(1)+O(1)=O(1); 
O(I)=O(N)*(O(F)+O(J))=O(N)*O(доминанты условия)=О(N); 
O(G)=O(N)*(O(C)+O(I)+O(K))=O(N)*(O(1)+O(N)+O(1))=O(N2); 
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N2)= O(N3); 
O(D)=O(A)+O(E)=O(1)+ O(N3)= O(N3)

Сложность данного алгоритма O(N3).

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

Эта информация может  использоваться программистом для  построения более эффективной программы  следующим образом. Прежде всего  можно попытаться сократить глубину  вложенности повторений. Затем следует рассмотреть возможность сокращения количества операторов в циклах с наибольшей глубиной вложенности. Если 90% времени выполнения составляет выполнение внутренних циклов, то 30%-ное сокращение этих небольших секций приводит к 90%*30%=27%-му снижению времени выполнения всей программы.

Это наиболее простой  пример.

Анализом эффективности  алгоритмов занимается отдельный раздел математики и найти наиболее оптимальную  функцию бывает не так - то и просто.

Оценим алгоритм бинарного поиска в массиве - дихотомию.

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

function search(low, high, key: integer): integer; 
var 
mid, data: integer; 
begin 
while low<=high do 
begin 
mid:=(low+high) div 2; 
data:=a[mid]; 
if key=data then 
search:=mid 
else 
if key < data then 
high:=mid-1 
else 
low:=mid+1; 
end; 
search:=-1; 
end;

Решение:

Первая итерация цикла имеет  дело со всем списком. Каждая последующая  итерация делит пополам размер подсписка. Так, размерами списка для алгоритма являются

n n/21 n/22 n/23 n/24 ... n/2m

В конце концов будет такое целое m, что

n/2m<2 или n<2m+1

Так как m - это первое целое, для  которого n/2m<2, то должно быть верно

n/2m-1>=2 или 2m=<n

Из этого следует, что  
2m=<n<2m+1 
Возьмем логарифм каждой части неравенства и получим 
m=<log2n=x<m+1 
Значение m - это наибольшее целое, которое =<х. 
Итак, O(log2n).

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

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

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