ВПЕРЁД ⇒
⇐ НАЗАД
Асимптотическая оценка сложности вычислений
Получая оценку для сложности вычислений какого-либо алгоритма, мы, в первую очередь, хотим узнать порядок роста для функции , вносящий решающий вклад в рост сложности вычислений рассматриваемого алгоритма. Можно даже сказать, что, оценивая функцию , мы ищем некоторые границы, за пределы которых функция не должна выходить.
Мы можем оценивать время работы алгоритма по разному, например:
- как время , которое для любого фиксированного усредняется по всем возможным экземплярам входных данных;
- как время , для любых значений которого рассматриваются только наихудшие варианты экземпляров входных данных, когда алгоритм отрабатывает медленней всего;
- как время , для любых значений которого рассматриваются только наилучшие варианты экземпляров входных данных, когда алгоритм отрабатывает быстрей всего.
- как время , получаемое для входных данных, обладающих некоторым определённым характером.
Поскольку поведение функции определяется её старшим членом (то есть порядком её роста), содержащим параметр , то целесообразно оценивать время работы алгоритма при больших значениях параметра (в идеале, при бесконечно больших значениях этого параметра), чтобы младшие члены функции не оказывали значимого влияния на её поведение. Соответственно, и ограничения функции лучше искать/оценивать для этих же больших значений параметра . В этом случае допустимо возникновение ситуаций, когда, при малых значениях параметра , функция будет выходить за пределы найденных ограничений по причине того, что на функцию оказывают сильное влияние её младшие члены, из-за которых и происходит выход за границы.
Оценка сложности вычислений алгоритма , полученная для размера входных данных , стремящегося к бесконечности, называется асимптотической оценкой сложности вычислений и показывает, к какому поведению стремится функция при достижении параметром предельных значений.
Если порядок роста функции говорит только о том, каким характером изменения/поведения обладает функция (рассматривается старшее слагаемое без множителя), то асимптотическая оценка сложности вычислений говорит о том, чему приблизительно равна функция с подобным характером изменения (множитель старшего слагаемого в этом случае учитывается).
Рассмотрим функцию . Эту функцию можно асимптотически оценить как , поскольку, при крайне больших значениях параметра , даже такое большое слагаемое как перестанет вносить значимый вклад в эту функцию. Поскольку коэффициент/множитель в члене никак не влияет на характер изменения (в данном случае, на квадратичность) функции и может быть любым, то говорим, что порядком роста функции является . Таким образом, получили: - асимптотическая оценка; - порядок роста. Для асимптотической оценки введём в рассмотрение новую функцию , в качестве аргумента которой будет задаваться порядок роста исходной функции (), и будем использовать обозначение новой функции в оценке сложности исходной зависимости :
Если мы положим, что , то это будет даже лучше, поскольку в этом случае функция будет точно отражать суть функции :
.
В приведённом примере мы можем обобщить/распространить полученный результат на любые значения множителя старшего члена и константного младшего члена:
Можно выделить два преимущества записи исходной функции в виде :
- Все незначащие множители и слагаемые убраны из рассмотрения и сокрыты под “капотом” функции .
- В качестве аргумента функции явным образом указывается порядок роста функции , благодаря чему моментально становится понятным, каким поведением обладает функция . В данном случае по самой форме записи можно без труда сделать вывод, что функция имеет порядок роста .
В рассмотренном примере нам удалось свести исходную функцию к функции , где - порядок роста функции . Мы можем обобщить/распространить этот пример на какие-угодно алгоритмы, для которых требуется найти их время работы .
Предположим, что нам известна исходная зависимость , оценку для которой хотелось бы получить. Тогда процесс получения оценки времени работы для любого алгоритма может быть сведён к следующим шагам:
- В исходной зависимости необходимо выделить главный член, соответствующий порядку роста функции . Пусть - порядок роста исходной зависимости .
- Для полученного порядка роста исходной зависимости необходимо найти/подобрать такую функцию , что .
Таким образом, получаем, что оценка времени работы алгоритма является композицией двух функций: - порядка роста функции ; - функции, которая при довольно точно описывает исходную функцию , то есть :
, где - композиция функций и ;
.
ВПЕРЁД ⇒
⇐ НАЗАД
Источники
- Павел Маврин “АиСД, Семестр 1, Лекция 1. Оценка времени. Сортировка слиянием”
- Big O нотация (Wiki)
- Томас Кормен “Алгоритмы. Построение и анализ”. Глава 2 “Приступаем к изучению”, параграф 2.2 “Анализ алгоритмов” (стр. 45-52).
Категория
Теги