КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Ресурсная эффективность алгоритмовОпределение ресурсной эффективности алгоритмов – необходимая составляющая этапа анализа разработанного программного обеспечения. Повышение ресурсной эффективности вычислительных алгоритмов актуально при обработке больших объемов данных, когда аппаратных и/или программных ресурсов может быть недостаточно для корректного завершения работы программного кода. Наиболее значимыми характеристиками ресурсной эффективности алгоритмов являются оценки временной и емкостной сложности, отражающие ресурсы процессора, оперативной памяти, а также внешних носителей данных (при использовании). Под трудоемкостью алгоритма А на входе D будем понимать количество элементарных операций, которые учитываются при анализе алгоритма. Под худшим случаем трудоемкости понимают наибольшее количество операций, задаваемых алгоритмом А на всех входах D определенной размерности n. Определим лучший случай трудоемкости, как наименьшее количество операций в аналогичном алгоритме и при той же размерности входа. Средний случай трудоемкости определяется средним количеством операций рассматриваемого алгоритма и входных данных. Зависимость трудоемкости алгоритма А от значения параметров на входе D определяет функцию трудоемкости алгоритма А для входа D. Классический анализ алгоритмов в данном контексте связан, прежде всего, с оценкой временной сложности. Большинство алгоритмов имеют основной параметр, который в значительной степени влияет на время выполнения операций. Если же определяющих параметров несколько, то, как правило, один их них выражается как функция от остальных. Иногда используют и такой подход: рассматривают только один параметр, считая остальные константами. Результатом анализа является асимптотическая оценка выполняемых алгоритмом операций в зависимости от длины входа, которая указывает порядок роста функции и результаты сравнения работы алгоритмов для больших данных. При этом оценка на реальных данных отличается от асимптотической тем, что она ориентирована на конкретные длины входов и число выполняемых алгоритмом операций. Временная сложность алгоритма определяется асимптотической оценкой функции трудоемкости алгоритма для худшего случая, обозначается O(f(n)) и читается как "О большое" или "О-нотация". Асимптотический класс функций О включает в себя как средний, так и лучший случай, потому что запись O(f(n)) обозначает класс функций, скорость роста которых не более, чем f(n) с точностью до некоторой положительной константы. В зависимости от вида функции f(n) выделяют следующие классы сложности алгоритмов.
На основании математических методов исследования асимптотических функций трудоемкости на бесконечности выделены пять классов алгоритмов. Класс 0 – это класс быстрых алгоритмов с постоянным временем выполнения, их функция трудоемкости O(1). Промежуточное состояние занимают алгоритмы со сложностью O(log N), которые также относят к данному классу. Класс Р – это класс рациональных или полиномиальных алгоритмов, функция трудоемкости которых определяется полиномиально от входных параметров. Например, O(N), O(N2, O(N3). Класс L – это класс субэкспоненциальных алгоритмов со степенью трудоемкости O(N log N). Класс E – это класс собственно экспоненциальных алгоритмов со степенью трудоемкости O(2N. Класс F – это класс собственно надэкспоненциальных алгоритмов. Существуют алгоритмы с факториальной трудоемкостью, но они в основном не имеют практического применения. Состояние памяти при выполнении алгоритма определяется значениями, требующими для размещения определенных участков. При этом в ходе решения задачи может быть задействовано дополнительное количество ячеек. Под объемом памяти, требуемым алгоритмом А для входа D, понимаем максимальное количество ячеек памяти, задействованных в ходе выполнения алгоритма. Емкостная сложность алгоритма определяется как асимптотическая оценка функции объема памяти алгоритма для худшего случая. Таким образом, ресурсная сложность алгоритма в худшем, среднем и лучшем случаях определяется как упорядоченная пара классов функций временной и емкостной сложности, заданных асимптотическими обозначениями и соответствующих рассматриваемому случаю.
|