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

Основные классы эффективности

Читайте также:
  1. B. Основные принципы исследования истории этических учений
  2. Biglnteger Классы
  3. I. Методические основы оценки эффективности инвестиционных проектов
  4. I. ОСНОВНЫЕ ПОНЯТИЯ (ТЕРМИНЫ) ЭКОЛОГИИ. ЕЕ СИСТЕМНОСТЬ
  5. I. Психологические условия эффективности боевой подготовки.
  6. I.3. Основные этапы исторического развития римского права
  7. II Съезд Советов, его основные решения. Первые шаги новой государственной власти в России (октябрь 1917 - первая половина 1918 гг.)
  8. II. Основные задачи и функции
  9. II. Основные задачи и функции
  10. II. Основные показатели деятельности лечебно-профилактических учреждений
  11. II. Основные проблемы, вызовы и риски. SWOT-анализ Республики Карелия
  12. II. Показатели эффективности инвестиционных проектов

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

Класс трудоемкости Вид функции трудоемкости Название подкласса Примечание Пример алгоритма данного подкласса
Полиномиальный класс (Р -класс) const   Алгоритм не зависит от длины входных параметров, то есть число операторов постоянно и не измениться не при каком случае.  
log n логарифмический Обычно такая зависимость появляется в результате сокращения размера задачи на постоянное значение на каждом шаге итерации алгоритма. Обратите внимание, что в логарифмическом алгоритме исключается работа со всеми входными данными Алгоритм бинарного поиска (метод деления отрезка пополам) среди n элементов.
n Линейная К этому подклассу относятся алгоритмы, выполняющие сканирование списка, состоящего из n элементов. Поиск элемента массива из n методом последовательного перебора
«n - логарифм n» К этому подклассу относятся большое количество алгоритмов декомпозиции, где для каждого из n элементов необходимо применить эффективный (например) поиск за логарифмическое время Эффективные алгоритмы сортировки: пирамидальная, фиксированное двухпутевое слияния
n 2 Квадратичная подобная зависимость характеризует эффективность алгоритмов, содержащих два вложенных цикла, каждый из которых выполняется не более n раз Простые схемы сортировки, например, пузырьковая,
Кубическая Как правило, подобная зависимость характеризует эффективность алгоритмов, содержащих три вложенных цикла Простой алгоритм перемножения матриц
Не детерминировано-полиномиальный (NP -класс) Экспоненциальная Данная зависимость типична для алгоритмов, выполняющих обработку всех подмножеств некоторого множества, состоящего из n элементов. Задача о ханойских башнях.
n! Факториальная Данная зависимость типична для алгоритмов, выполняющих обработку всех перестановок некоторого множе­ства, состоящего из n элементов Полный перебор всех сочетаний элементов исходного множества при поиске решения задачи.
Часто термин "экспоненциальный" используется в широком смысле (в том числе и для всего класса) и означает очень высокие порядки роста, имеющий принципиально другой характер поведения по сравнению с полиномом некоторой степени.

 

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

Таблица 1

   
   
   
   

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

log a n = loga b log b n.

Поэтому далее будем опускать основание логарифма, то есть log n.

Если считать, что числа соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму со временем работы T (log n) потребуется 20 микросекунд, а алгоритму со временем работы T (n 2) – более 12 дней.

Существует и другая крайность: показательная функция 2n и функция n! – вычисление факториала. Обе эти функции имеют настолько высокий порядок роста, что его значение становится астрономически большим уже при умеренных зна­чениях n. Например, чтобы выполнить 2100 операций компьютеру, имеющему производительность в один триллион операций в секунду, понадобиться без малого 4 • 1010 лет! Однако это ничто по сравнению со временем, которое затратит тот же компьютер на выполнение 100! операций.

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

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

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



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