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

Лучший, средний и худший случаи очень большое влияние играют в сортировке. 
Объем вычислений при сортировке

O-анализ сложности  получил широкое распространение  во многих практических приложениях.  Тем не менее необходимо четко  понимать его ограниченность.

К основным недостаткам подхода  можно отнести следующие: 
1) для сложных алгоритмов получение O-оценок, как правило, либо очень трудоемко, либо практически невозможно, 
2) часто трудно определить сложность "в среднем", 
3) O-оценки слишком грубые для отображения более тонких отличий алгоритмов, 
4) O-анализ дает слишком мало информации (или вовсе ее не дает) для анализа поведения алгоритмов при обработке небольших объемов данных.

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

Еще одна сложность - определение "среднего случая". Обычно сделать это достаточно трудно из-за невозможности предсказания условий работы алгоритма. Иногда алгоритм используется как фрагмент большой, сложной программы. Иногда эффективность работы аппаратуры и/или операционной системы, или некоторой компоненты компилятора существенно влияет на сложность алгоритма. Часто один и тот же алгоритм может использоваться в множестве различных приложений.

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

Возможно, основным недостатком O-функций является их черезмерная  грубость. Если алгоритм А выполняет некоторую задачу за 0.001*N с, в то время как для ее же решения с помощью алгоритма В требуется 1000*N с, то В в миллион раз быстрее, чем А. Тем не менее А и В имеют одну и ту же временную сложность O(N).

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

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

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

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

Алгоритм быстрой сортировки характеризуется также и большей  интеллектуальной сложностью по сравнению  с алгоритмом сортировки вставками. Если предложить сотне людей отсортировать  последовательность объектов, то вероятнее всего, большинство из них используют алгоритм сортировки выборками. Маловероятно также, что кто-то из них воспользуется быстрой сортировкой. Причины большей интеллектуальной и пространственной сложности быстрой сортировки очевидны: алгоритм рекурсивный, его достаточно трудно описать, алгоритм длиннее (имеется в виду текст программы), чем более простые алгоритмы сортировки.

 

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

ВАРИАНТ 11

Задание 1

Пронумеруем реквизиты  каждого документа (Р1, Р2, Р3, Р4, Р5, P6) и установим их значность. Результаты представлены в соответствующих таблицах:

Таблица 1 – Список филиалов сбербанка

№ реквизита	Р1	Р2	P3
Наименование  реквизита	Номер филиала	Адрес	Телефон
Значность реквизита	2	25	11
Значение  реквизита	22	Улица Малахова дом 22	22-22-22
	23	Улица Хмелева дом 33	33-33-33
	24	Улица Маннаного дом 44	44-44-44
	25	Улица Чингисса дом  77	77-77-77

Таблица 2 – Справочник плательщиков

№ реквизита	Р1	Р2	Р3	Р4
Наименование  реквизита	Код плательщика	ФИО плательщика	Домашний адрес	Номера счетов для  оплаты за
				воду	газ	отопление	эл.энергию
Значность реквизита	4	30	25	4	4	4	4
Значение  реквизита	1242	Капустин  А.А	Ул.Зелёная	4201	4202	4203	4204
	1333	Шевчук Б.А	Ул.Красная	3371	3372	3373	3374
	1242	Лапшин М.Ю	Ул. Чаева	2356	2357	2358	2359

 

Таблица 3 – Список услуг

№ реквизита	P1	Р2
Наименование  реквизита	№  п/п	Название  услуги
Значность реквизита	2	15
Значение  реквизита	1	Водоснабжение
	2	Электроэнергия
	3	Отопление
	4	Газоснабжение

Таблица 4 – Квитанция об оплате услуг

№ реквизита	Р1	Р2	Р3	Р4	Р5	Р6	Р7	Р8
Наименование  реквизита	Номер филиала Сбербанка	Дата оплаты	ФИО клиента	Домашний адрес клиента	Название коммунальной услуги	Номер счета	Месяц, за который производится оплата	Сумма оплаты
Значность реквизита	2	10	30	25	4	4	2	10
Значение  реквизита	24	02.02.2011		ул. Зеленая 48 кв. 64	водоснабжение	4201	01

Определим среднюю информационную емкость документа (среднее количество символов в документе) по формуле:

, где

q_ij– количество символов в j-ом реквизите i-ого документа,

                      k_i – число строк в i-ом документе,

                      m – количество реквизитов в документе,

                      n – количество рассматриваемых документов.

 

Q = ( 2*4+2*25+2*11  +  3*4+3*30+3*25+3*4+3*4+3*4+3*4  +  4*2+4*15  +  2+10+30+25+4+4+2+10  ) / 4 =   115 символов.

 

Задание 2

 На основе анализа  информационных процессов, происходящих  в ПрО, выделить объекты ПрО  и их атрибуты, выявить  связи  (отношения) между объектами. Построить  инфологическую модель ПрО в  виде ER – диаграммы (модель «объекты – связи»).

Объекты ПрО представлены в виде таблиц 1-4,  атрибуты объектов – наименования столбцов таблиц. Инфологическая модель ПрО в виде ER – диаграммы представлена на рисунке1.

 

 1

 1

1 1

 1 

 

 м

 

                                                                               

                                                                                                                                                                                                            

                                                                                                                                               

                                                                   м                                          

 

 

 

 

Рисунок1 – ER – диаграмма ПрО «Товары»

Описание структуры атрибутов

Описание атрибутов, таблицы, Квитанция оплаты услуг представлено на рисунке 2.

 

Рисунок 2 – Атрибуты таблицы квитанция оплаты услуг

Описание атрибутов, таблицы, Список услуг представлено на  рисунке 3.

 

Рисунок 3 – Атрибуты таблицы список услуг

  Описание атрибутов, таблицы, Список филиалов Сбербанка представлено на рисунке 3.

 

Рисунок 3 – Атрибуты таблицы список филиалов Сбербанка

Описание атрибутов, таблицы, Справочник плательщиков представлено на рисунке 3.

 

Рисунок 5 – Атрибуты таблицы справочник плательщиков

3. Свойства отношений между объектами описать в виде следующей таблицы:

Свойства отношений  между оьъектами ПрО

№ п/п	Название отношения	Объекты, связанные отношением		Тип отношения
		название объекта 1	название объекта 2
1	Содержат	Список филиалов	Список услуг	функциональные
2	Предъявляет	Плательщик	Справочник плательщика	временные
3	Получает	Плательщик	Квитанция	временные
4	Выбирает	Плательщик	Список филиалов	временные

 

4. Инфологическую модель  ПрО в виде ER – диаграммы отобразить в среде реляционной БД (РБД) в виде совокупности схем отношений с указанием ключевых атрибутов:

Список филиалов Сбербанка (Номер филиала, Адрес, Телефон)

Справочник плательщика (Код плательщика, ФИО плательщика, Домашний адрес, Вода, Газ, Электроэнергия)

Список услуг (№ подпункта, название услуги)

Квитанция об оплате услуг (Номер филиала сбербанка, Дата оплаты, ФИО клиента, Домашний адрес клиента, Название коммунальной услуги, Номер счёта, Месяц за который производится оплата, Сумма платежа).

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

 

Рисунок 6 – Схема данных

 

 

 

 

 

 

 

 

 

 

 

 

Задание 3

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

а)    представить информацию о клиентах, проживающих по ул. Зелёной;

б)   вывести дату оплаты, а также адресы, телефон  кассы, в которой клиент Шевчук Б.А. уплатил за газ за январь текущего года;

в)   во вновь созданную  таблицу архив перенести информацию об оплате электроэнергии за январь месяц  текущего года.

Запрос клиентов проживающих  по улице Зелёной представлен  на рисунке 8.

 

Рисунок 8 – Запрос клиентов проживающих по ул.Зелёной

Запрос даты оплаты Шевчуком за газ за январь текущего года представлен на рисунке 9.

Рисунок 9 – Запрос даты оплаты за январь

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

Рисунок 10 – Архив оплаты

Данные запросы реализованы  в реляционной СУБД Microsoft Access.

 

Задание 4

1. Выполнить сортировку  реквизита методом турниров, простых вставок, пузырька.  

 

Код плательщика

1380

2341

1012

2643

2154

2425

1826

1117

1158

1429

1340