Реклама на сайте (разместить):



Реклама и пожертвования позволяют нам быть независимыми!

Угловая мера асимптотического роста функций и ее свойства

Материал из Викизнание
Перейти к: навигация, поиск
Эвентология
Открытый Helgus~µастер~Kласс — H~µ~K
Это незавершённая статья из области эвентологии и её применений, редактируемая при участии Мастера

Отыскание функций сложности алгоритмов важно как с теоретической, так и с практической точек зрения. С теоретической точки зрения интересен вопрос: как далеко для данной задачи можно продвигаться по пути уменьшения сложности алгоритмов ее решения. С практической точки зрения важен порядок роста функции сложности t(n) c возрастанием параметра n. Действительно, на практике нет необходимости в точном построении выражения для функции сложности, что зачастую выполнить непросто. Использование приближенного представления оправдано тем, что возникающей ошибкой можно пренебречь. На практике применяют асимптотические оценки функций сложности.

Традиционная классификация алгоритмов основана на асимптотических оценках их функций сложности, причем в качестве разделяющей взята степен-ная функция с неотрицательным казателем. Такое разграничение позволяет выделить низкозатратные (с точки зрения вычислительных ресурсов) – полиномиальные алгоритмы и высокозатратные – экспоненциальные алгоритмы. Сегодняшнее время стремительного развития вычислительной техники и информационных технологий диктует необходимость более детального разграничения сложностных классов алгоритмов. Так, в криптографических системах широкое практическое применение уже находят субэкспоненциальные алгоритмы – алгоритмы с более чем полиномиальной, но менее чем экспоненциальной сложностью. В настоящее время широкое применение получили алгоритмы функция сложности которых растет медленнее чем у полиномов. Так же следовало бы выделить класс алгоритмов функция сложности которых растет намного быстрее чем у экспоненты.

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

Известны попытки введения детальной классификации алгоритмов, удовлетворяющей указанным требованиям. Например, Головешкин В.А. и Ульянов М.В. предложили в качестве классификационного признака использовать значение угловой меры асимптотического роста функций сложности.


Угловая мера[править]

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

Обозначим через n длину входа алгоритма, а через f=f(n) – функцию сложности алгоритма. В рамках дальнейшего изложения будем считать, что аргумент x непрерывен, т. е. f=f(x), а необходимые значения функции f(x) вычисляются в целочисленных точках x=n. Для разграничения полиномов и экспонент предлагается использовать функцию степенного логарифма g(x)=(lnx)^{{lnx}}.

Утверждение 1. Функция степенного логарифма g(x)=(lnx)^{{lnx}} является разграничивающей для полиномов и экспонент.

Доказательство. Утверждение эквивалентно тому, что функция g(x) удовлетворяет следующим двум соотношениям при x → ∞: если f(x)=x^{k}, k>0, то f(x)=o(g(x)) (1)

если f(x)=e^{{k\lambda }}, k>0, то g(x)=o(f(x))(2)

Для доказательства этих соотношений воспользуемся леммой о логарифмическом пределе: если \lim _{{n\to \infty }}f(x)=\infty , и \lim _{{n\to \infty }}g(x)=\infty , то если \lim _{{n\to \infty }}{\frac  {lnf(x)}{lng(x)}}=0, то \lim _{{n\to \infty }}{\frac  {f(x)}{g(x)}}=0, т. е. f(x)=o(g(x)).

На основании этой леммы покажем справедливость соотношения (1):

\lim _{{n\to \infty }}{\frac  {ln(x^{k})}{ln((lnx)^{{lnx}})}}=\lim _{{n\to \infty }}{\frac  {kln(x)}{lnx(lnlnx)}}=\lim _{{n\to \infty }}{\frac  {k}{ln(lnx)=0}},

следовательно, x^{k}=o((lnx)^{{lnx}}) при k>0, и соотношения (2):

\lim _{{n\to \infty }}{\frac  {ln((lnx)^{{lnx}})}{ln(e^{{x\lambda }})}}=\lim _{{n\to \infty }}{\frac  {ln(x)ln(lnx)}{x\lambda }}=0,

следовательно, (lnx)^{{lnx}}=o(e^{{x\lambda }}) при \lambda >0. Утверждение 1 доказано.

Угловая мера асимптотического роста функции вводится следующим образом: пусть дана функция f(x)≥ 0, монотонно возрастающая, и \lim _{{n\to \infty }}f(x)=\infty . Поставим ей в соответствие функцию

h(x)=ln(f(x))+{\frac  {xln(f(x))}{ln(f(x))+lnx}} (3)

Функция h(x)обладает следующими свойствами, которые устанавлива-ются двумя леммами.

Лемма 1. Пусть f(x)=e^{{x\lambda }}(1+\gamma (x)), где \lambda >0,\gamma (x)=o(1), \gamma '(x)=o(1) при x\to \infty , тогда \lim _{{n\to \infty }}h'(x)=\lambda +1 .


Лемма 2. Пусть f(x)=x^{k}(1+\gamma (x)), где \gamma (x)=o(1), \gamma '(x)=o(1) x\gamma '(x)=O(1) при x\to \infty , тогда \lim _{{n\to \infty }}h'(x)={\frac  {k}{k+1}} .

Равенство константе предела производной функции h(x) как для полиномов, так и для экспонент позволяет доказать следующую лемму, вводящую преобразование координатной системы.

Лемма 3. Пусть дана функция h(x), такая, что \lim _{{n\to \infty }}h'(x)=K, где K>0. Рассмотрим образованную на основе функции h(x) параметрически заданную функцию z(s), определенную следующим образом:

\lim _{{n\to \infty }}{\frac  {\partial z}{\partial s}}={\frac  {1}{K}}

где s=\arctan({\frac  {1}{x}}) z=\arctan({\frac  {1}{h(x)}}) (4)

Графически полученный результат в лемме 3 может быть интерпретирован следующим образом. В системе координат (z,s) полиномы и экспоненты отображаются в функции, имеющие в асимптотике при x → ∞,s → 0 разные углы наклона касательной в точке (z=0, s=0), что и определило название угловой меры асимптотического роста функций.

Леммы 1, 2 и 3 служат основой следующей теоремы.

Теорема 1 (об угловой мере асимптотического роста функций). Пусть дана функция f(x), монотонно возрастающая, и \lim _{{n\to \infty }}f(x)=\infty . Определим меру \pi (f(x)) асимптотического (на бесконечности) роста функции

f(x)\pi (f(x))=\pi -2\arctan(R),

где R=\lim _{{n\to \infty }}f(x)=\infty , где параметрически заданная функция z(s) определена в виде (4), а функция h(x) задана по функции f(x) cледующим образом:

h(x)=ln(f(x))+{\frac  {xln(f(x))}{ln(f(x))+lnx}},

тогда если

1)f(x)=e^{{x\lambda }}(1+\gamma (x)), где \lambda >0,\gamma (x)=o(1), \gamma '(x)=o(1) при x\to \infty , то \pi /2<\pi (f(x))<\pi ;

2)f(x)=x^{k}(1+\gamma (x)), где \gamma (x)=o(1), \gamma '(x)=o(1) x\gamma '(x)=O(1) при x\to \infty , то 0<\pi (f(x))<\pi /2;

3)f(x)=lnx^{{lnx}} , то \pi (f(x))=\pi /2.

Свойства угловой меры асимптотического роста функций[править]

Предложенная угловая мера асимптотического роста функций обладает рядом свойств, которые позволяют использовать ее для построения классификации алгоритмов по сложности функции трудоемкости. На базе введенной меры \pi (f(x)), можно определим следующие пять функциональных множеств в предложении, что \lim _{{n\to \infty }}f(x)=\infty .

1)Определим множество функций

FZ:FZ=\{f(x)|f(x)\prec x^{k},\forall k>0\}.

Для функции f(x) из множества FZ значение R, определяемое по лемме 3, равно +\infty , и мера \pi (f(x))=\pi +2arctan(R)=0\forall f(x)\in FZ, в частности, \pi (ln(x))=0.

2)Определим множество полиномов

FP:FP=\{f(x)|\exists k>0:f(x)=\theta (x^{k})\}.

Данное определение базируется на лемме 2, однако можно показать, что предложенная мера остается в силе и для более широкого класса функций вида f(x)=\theta (x^{k})g(x), где g(x)\in FZ, тогда множество FP может быть определено следующим образом. Вначале определим множество функций

F_{k}:F_{k}=\{f(x)|x^{{k-\varepsilon }}\prec f(x)\prec x^{{k+\varepsilon }},k>0,\varepsilon \to +0,x\to +\infty \}

и на его основе определим множество обобщенных полиномов

FP:FP=\{f(x)|\exists k>0:f(x)\in F_{k}\};

для функции f(x) из множества FP значение R=k+1/k,k>0, по леммам 2, 3, и мера \pi (f(x))=\pi -2arctan((k+1)/k), следовательно 0<\pi (f(x))<\pi /2.

3)Определим множество функций

FL:FL=\{f(x)|x^{k}\prec f(x)\prec e^{{x\lambda }},\forall k>0,\forall \lambda >0\}.

Для функции f(x) из FL значение R, определяемое по лемме 3, равно 1, и мера \pi (f(x))=\pi -2arctan(1)=\pi /2,в частности, \pi (lnx^{{lnx}})=\pi /2.

4)Определим множество экспонент

FE:FE=\{f(x)|\exists \lambda >0:f(x)=\theta (e^{{x\lambda }})\}.

Данное определение базируется на лемме 1, однако можно показать, что предложенная мера остается в силе и для более широкого класса функций вида f(x)=theta(e^{{x\lambda }})g(x), где g(x)\in \{FZ,FP,FL\}, тогда множество FE может быть определено следующим образом. Вначале определим множество функций

F_{\lambda }:F_{\lambda }=\{f(x)|e^{{(\lambda -\varepsilon )x}}\prec f(x)\prec e^{{(\lambda +\varepsilon )x}},\lambda >0,\varepsilon \to +0,x\to +\infty \}

и на его основе определим множество обобщенных экспонент

FE:FE=\{f(x)|\exists \lambda >0:f(x)\in F_{\lambda }\}.

Для функции f(x) из FE значение R=1/(1+\lambda ), \lambda >0 по леммам 1 и 3, и мера \pi (f(x))=\pi -2arctan(1/(1+\lambda )), следовательно \pi /2<\pi (f(x))<\pi .

5)Определим множество функций

FF:FF=\{f(x)|e^{{x\lambda }}\prec f(x),\forall \lambda >0\}.

Для функции f(x) из FF значение R, определяемое по лемме 3, равно 0, и мера \pi (f(x))=\pi -2arctan(R)=\pi ,в частности, \pi (x^{x})=\pi .

Укажем свойства, которыми обладает введенная угловая мера асимптотического роста функций – \pi (f(x)):

- Мера принимает значение, равное \pi /4, для степени k={\sqrt  {2}}/2;

- Мера \pi (x^{k}) принимает значение, равное 3\pi /4, при показателе \lambda ={\sqrt  {2}};

- Мера \pi (f(x)) обладает интересным свойством:

\pi (x^{{1\lambda }})+\pi (e^{{x\lambda }})=\pi , в частности, \pi (x)+\pi (e)=\pi .

Классификация алгоритмов по сложности функции трудоемкости[править]

Использование угловой меры асимптотического роста функций \pi f(x) позволяет предложить следующую классификацию алгоритмов по асимптотике роста функции трудоемкости. Сохраняя общепринятое обозначение n для размерности входа алгоритма А, обозначая через f_{A}^{*}(n) функцию сложности и подразумевая формальный переход от n к x при вычислении \pi f(x), введем следующее теоретико-множественное определение классов.

1. Класс \pi 0 (пи нуль) – класс «быстрых алгоритмов» - это алгоритмы, для которых функции сложности принадлежат множеству FZ и имеют меру ноль:

\pi 0=\{A|\pi (f_{A}^{*}(n))=0\Leftrightarrow f_{A}^{*}(n)\in FZ\}.

Алгоритмы, принадлежащие этому классу, являются существенно быстрыми относительно длины входа; в основном это алгоритмы, имеющие полилогарифмическую или логарифмическую сложность.

2. Класс \pi P – класс «рациональных (собственно полиномиальных) алгоритмов» - это алгоритмы, функции сложности которых принадлежат множеству FP:

\pi P=\{A|0<\pi (f_{A}^{*}(n))<\pi /2\Leftrightarrow f_{A}^{*}(n)\in FP\}.

К этому классу относится большинство реально используемых алгоритмов, позволяющих решать вычислительные задачи за рациональное время. Введенный класс алгоритмов \pi P является подклассом алгоритмов, определяющих класс задач P в теории сложности вычислений.

3. Класс \pi L – класс «субэкспоненциальных алгоритмов» - это алгоритмы, функции сложности которых принадлежат множеству FL:

\pi L=\{A|\pi (f_{A}^{*}(n))=\pi /2\Leftrightarrow f_{A}^{*}(n)\in FL\}.

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

Обозначение L в названии класса отражает тот факт, что функция степенного логарифма g(x)=(lnx)^{{lnx}} является одной из функций, разграничивающих полиномы и экспоненты.

4. Класс \pi E – класс «собственно экспоненциальных алгоритмов» - это алгоритмы, функции сложности которых принадлежат множеству FE:

\pi E=\{A|\pi /2<\pi (f_{A}^{*}(n))=\pi \Leftrightarrow f_{A}^{*}(n)\in FE\}.

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

5. Класс \pi F – класс «надэкспоненциальных алгоритмов» - это алгоритмы, функции сложности которых принадлежат множеству FF:

\pi F=\{A|\pi (f_{A}^{*}(n))=\pi \Leftrightarrow f_{A}^{*}(n)\in FF\}.

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

Статью можно улучшить?
✍ Редактировать 💸 Спонсировать 🔔 Подписаться 📩 Переслать 💬 Обсудить
Позвать друзей
Вам также может быть интересно: