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

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

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

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

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

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

В записи O(·) можно легко дать определение полиномиального времени: алгоритмом с полиномиальным временем называется алгоритм, время выполнения которого T(n) = O(nd) для некоторой константы d, не зависящей от размера входных данных.

Таким образом, алгоритмы с границами времени выполнения вида O(n2) и O(n3) являются алгоритмами с полиномиальным временем.

Однако важно понимать, что алгоритм может выполняться с полиномиальным временем даже в том случае, если время выполнения не записывается в форме n в целочисленной степени.

Прежде всего, многие алгоритмы имеют время выполнения в форме O(nx) для некоторого числа x, которое не является целым. Например, в главе 5 представлен алгоритм с временем выполнения O(n1,59); также встречаются экспоненты меньшие 1, как в границах типа O() = O(n1/2).

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

Другими словами, если алгоритм имеет время выполнения O(n log n), он также имеет время выполнения O(n2), а следовательно, является алгоритмом с полиномиальным временем.