Между полиномом и экспонентой

Сообщение №4391 от Шамиль 06 августа 2002 г. 15:56
Тема: Между полиномом и экспонентой

Какие функции растут быстрее любого полинома и медленнее любой экспоненты? Это для NP-проблемы.


Отклики на это сообщение:

> Какие функции растут быстрее любого полинома и медленнее любой экспоненты? Это для NP-проблемы.
Например, exp(x)/x


> > Какие функции растут быстрее любого полинома и медленнее любой экспоненты? Это для NP-проблемы.
> Например, exp(x)/x
Между константой и самой медленной степенной функцией лежит логарифм.
Нет ли между X^n ... exp(x)/x^m < exp(x) там, где многоточие. Ничего придумать не могу


> > > Какие функции растут быстрее любого полинома и медленнее любой экспоненты? Это для NP-проблемы.
> > Например, exp(x)/x
> Между константой и самой медленной степенной функцией лежит логарифм.
> Нет ли между X^n ... exp(x)/x^m < exp(x) там, где многоточие. Ничего придумать не могу

X^n


> > Какие функции растут быстрее любого полинома и медленнее любой экспоненты? Это для NP-проблемы.
> Например, exp(x)/x

Пример некорректен. Какая нибудь exp(x/2) растет быстрее указанной в примере.
Шамиль, а может рассмотреть какие-то спецфункции? например, заданных каким-нибудь диффуром?



> Пример некорректен. Какая нибудь exp(x/2) растет быстрее указанной в примере.
> Шамиль, а может рассмотреть какие-то спецфункции? например, заданных каким-нибудь диффуром?

Ну так и требуется же, чтобы функция росла медленнее любой экспоненты. Так что все правильно.
А насчет спецфункции... Насколько я понял, речь идет об NP-полноте. Наврядли можно придумать алгоритм с такой временной сложностью.


>
> > Пример некорректен. Какая нибудь exp(x/2) растет быстрее указанной в примере.
> > Шамиль, а может рассмотреть какие-то спецфункции? например, заданных каким-нибудь диффуром?

> Ну так и требуется же, чтобы функция росла медленнее любой экспоненты. Так что все правильно.
> А насчет спецфункции... Насколько я понял, речь идет об NP-полноте. Наврядли можно придумать алгоритм с такой временной сложностью.
Алгоритм придумать - запросто. Но кому он такой медленный нужен, почти что перебор?


В алгоритмы я влезать не буду..
Но вопрос был такой:
найти функцию промежуточного роста между х^n и exp(ax) для сколь угодно большого n и сколь угодно малого параметра a.

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


> В алгоритмы я влезать не буду..
> Но вопрос был такой:
> найти функцию промежуточного роста между х^n и exp(ax) для сколь угодно большого n и сколь угодно малого параметра a.

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

А прологарифмировать слабо?
А потом между n log x и ax разве ничего асимптотически хорошего не вставляется?
Типа корень квадратный ...



> А прологарифмировать слабо?
> А потом между n log x и ax разве ничего асимптотически хорошего не вставляется?
> Типа корень квадратный ...
Хмх, типа ехр(x^1/2)..
Вставляется, Михалыч прав.. а мне показалось, что тут нечто особенное зарыто :(.
Я даже пример придумал: f(x)=tg(pi/2*(x/(1+x))).
Кстати, попробовал полопиталить, но ничего путного не вышло.
А дальше мне лень рыть.... Так сразу не скажешь, что быстрее растет..
И вообще, может эта штучка быстрее любой экспоненты растет..
Не подскажете, знатоки, у вас глаз более наметан?


>
> > А прологарифмировать слабо?
> > А потом между n log x и ax разве ничего асимптотически хорошего не вставляется?
> > Типа корень квадратный ...
> Хмх, типа ехр(x^1/2)..
> Вставляется, Михалыч прав.. а мне показалось, что тут нечто особенное зарыто :(.
> Я даже пример придумал: f(x)=tg(pi/2*(x/(1+x))).
> Кстати, попробовал полопиталить, но ничего путного не вышло.
> А дальше мне лень рыть.... Так сразу не скажешь, что быстрее растет..
> И вообще, может эта штучка быстрее любой экспоненты растет..
> Не подскажете, знатоки, у вас глаз более наметан?

f(x)=tg(pi/2-pi/(2+2x))=ctg(pi/(2+2x))=cos(pi/(2+2x))/sin(pi/(2+2x))=
=(1+O((pi/(2+2x))^2))/(pi/(2+2x)+...)=O(x)


> > > > Какие функции растут быстрее любого полинома и медленнее любой экспоненты? Это для NP-проблемы.
> > > Например, exp(x)/x
> > Между константой и самой медленной степенной функцией лежит логарифм.
> > Нет ли между X^n ... exp(x)/x^m < exp(x) там, где многоточие. Ничего придумать не могу

> X^n
Спасибо. Всё понял. Нужно логарифмировать. Функций сколько угодно.


> >
> > > А прологарифмировать слабо?
> > > А потом между n log x и ax разве ничего асимптотически хорошего не вставляется?
> > > Типа корень квадратный ...
> > Хмх, типа ехр(x^1/2)..
> > Вставляется, Михалыч прав.. а мне показалось, что тут нечто особенное зарыто :(.
> > Я даже пример придумал: f(x)=tg(pi/2*(x/(1+x))).
> > Кстати, попробовал полопиталить, но ничего путного не вышло.
> > А дальше мне лень рыть.... Так сразу не скажешь, что быстрее растет..
> > И вообще, может эта штучка быстрее любой экспоненты растет..
> > Не подскажете, знатоки, у вас глаз более наметан?

> f(x)=tg(pi/2-pi/(2+2x))=ctg(pi/(2+2x))=cos(pi/(2+2x))/sin(pi/(2+2x))=
> =(1+O((pi/(2+2x))^2))/(pi/(2+2x)+...)=O(x)

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


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100