АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Функция сложности алгоритма

Читайте также:
  1. I Функция
  2. Адресная функция
  3. Аналитическая функция
  4. Антиномии языка как проявление его сложности
  5. Архитектура, управляемая событиями. Типы данных Win32. Оконная процедура (функция). Оконный класс.
  6. Б) система; г) функция.
  7. Бенедикт Андерсон: национализм и репрессивно-мобилизационная функция историографии
  8. Бесконечно большие функции и их связь с бесконечно малыми функциями.
  9. В уголовном судопроизводстве функция обвинения отделена от функции защиты, а обе они отделены от функции рассмотрения дела судом.
  10. Взаимосвязь с другими функциями организации
  11. Внимание как высшая психическая функция, по Л.С. Выготскому
  12. Внимание как функция умственного контроля, по П.Я. Гальперину

В.П. Пинчук

Анализ и построение алгоритмов. Краткий конспект лекций -

Запорожье: ЗНТУ, 2012.

 

Математический анализ Алгоритмов

 

1. Функция сложности алгоритма

2. Асимптотические классы и отношения

3. Базовые теоремы

4. Сложность задач

 

 

Функция сложности алгоритма

 

Рассмотрим некоторую задачу Р и алгоритм АР, который решает эту задачу. Для оценивания эффективности алгоритма Ар используют т.н. функции сложности: функцию временной сложности Ft(n) и функцию пространственной сложности Fs(n). Значением функции Ft(n) является время работы алгоритма, а функции Fs(n) - объем используемой памяти. Аргументом функции сложности в обоих случаях является размер входа алгоритма.

Для анализа алгоритмов важными являются следующие свойства функция сложности.

1 Функция F(n) является отображением вида F: A®B, где A,B = [0, +¥].

2. Функция F(n) является неубывающей при достаточно больших n: т.е. существует такое n0>0, что для любых n1, n2 > n0 и n1 > n2 имеет место F(n1) ³ F(n2).

 

Далее под функцией сложности понимаем функцию временной сложности.

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

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

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

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

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

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

 

 


1 | 2 | 3 | 4 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)