Полиномиальные функции

Напомним, что полиномиальной называется функция, которая может быть за- писана в форме f (n) = a0 + a n + a2n2 + ...+ ad nd для некоторой целочисленной константы d > 0, где последний коэффициент ad отличен от нуля.
Значение d называется степенью (или порядком) полинома. Например, упоминавшиеся ранее функции видаpn2 + qn + r (где p ф 0) представляют собой полиномиальные функции со степенью 2.

Основная особенность полиномиальных функций заключается в том, что их асимптотическая скорость роста детерминируется «членом высшего порядка» — то есть слагаемым, определяющим степень. Это утверждение более формально определяется в следующем утверждении. Так как нас интересуют только функции,

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

(2.7) Предположим, f является полиномиальной функцией степени d с поло- жительным коэффициентом ad. В этом случае f = O(nd).

Доказательство. Условие записывается в виде f = a0 + a1n + a2n2 + ...+ adnd, где ad > 0. Верхняя граница напрямую следует из (2.5). Во-первых, следует заметить, что коэффициенты a. для j < d могут быть отрицательными, но в любом случае anj < \aj\nd для всех n > 1. Следовательно, каждый член полинома имеет O(nd). Так как f представляет собой сумму фиксированного количества функций, каждая из которых имеет O(nd), из (2.5) следует, что f = O(nd). ■

Также можно показать, что по условиям (2.7) f = Ω(nd), из чего следует, что фактически f = 0(nd).

Это свойство играет важную роль для рассмотрения отношения между асимпто- тическими границами такого рода и понятием полиномиального времени, к кото- рому мы пришли в предыдущем разделе, для формализации более расплывчатого понятия эффективности. В записи O() можно легко дать определение полиноми- ального времени: алгоритмом с полиномиальным временем называется алгоритм, время выполнения которого T(n) = O(nd) для некоторой константы d, не зависящей от размера входных данных.

Таким образом, алгоритмы с границами времени выполнения вида O(n2) и O(n3) являются алгоритмами с полиномиальным временем. Однако важно понимать, что алгоритм может выполняться с полиномиальным временем даже в том случае, если время выполнения не записывается в форме n в целочисленной степени. Прежде всего, многие алгоритмы имеют время выполнения в форме O(n?) для некоторого числа X, которое не является целым. Например, в главе 5 представлен алгоритм с временем выполнения O(;?1'59); также встречаются экспоненты меньшие 1, как в границах типа O( v'п ) = 0(ni/2).

Другой распространенный пример: часто встречаются алгоритмы, время вы- полнения которых записывается в форме O(n log n). Такие алгоритмы также имеют полиномиальное время выполнения: как будет показано далее, log n < n для всех n > 1, а следовательно, n log n < n2 для всех n > 1. Другими словами, если алгоритм имеет время выполнения O(n log n), он также имеет время выполнения O(n2), а сле- довательно, является алгоритмом с полиномиальным временем.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Полиномиальные функции:

  1. Функции журналистики. Понятие функцию Многообразие социальных и информационных потребностей общества – объективная основа функций журналистики.
  2. “Не язык — функция поэта, а поэт — функция языка”
  3. 1.1.2. Функции социологии
  4. РЕЧЬ: ФУНКЦИЯ ПРЕДИКАТИВНАЯ
  5. ФУНКЦИЯ ПСИХИЧЕСКАЯ НАТУРАЛЬНАЯ
  6. ФУНКЦИЯ ПСИХОФИЗИОЛОГИЧЕСКАЯ
  7. Иерархия функций
  8. Функции управления в организации.
  9. ФУНКЦИЯ ВЕГЕТАТИВНАЯ
  10. Тема 4. Функции сравнительного правоведения
  11. ФУНКЦИЯ ПСИХИЧЕСКАЯ: ЛОКАЛИЗАЦИЯ
  12. Дисфункции и латентные функции
  13. 11.2.3. Функции религии
  14. Функции типа
  15. ФУНКЦИИ КОНТРОЛЯ
  16. Функции телевидения
  17. ФУНКЦИЯ ПСИХИЧЕСКАЯ: КОМПЕНСАЦИЯ