Полиномиальные функции
Напомним, что полиномиальной называется функция, которая может быть записана в форме 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), а следовательно, является алгоритмом с полиномиальным временем.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу