Асимптотическое поведение функции

[ccoder]

Помогите пожалуйста разобраться.
Есть

$$\[f\left( n \right) = {4^{\sqrt n }},g\left( n \right) = {2^{\frac{n} {{{{\log }_2}\left( n \right)}}}}\]$$

Нужно заполнить таблицу

Вписать + или -, в зависимости от поведения.

Пробую рассмотреть так
Получаю графики

где
$f(x)$ - зелёный, $g(x)$ - красный
Точка пересечения графиков $x = 2.04, y = 7.26$
Предел не существует

$$\[\mathop {\lim }\limits_{n \to \infty } \frac{{f\left( n \right)}} {{g\left( n \right)}}\] $$

Заполнил вот так, но очень сомневаюсь


Как это всё дело правильно сделать?

[ccoder]

??

[Sonic86]

Я вместо картинок вижу жабу в кубике.

Вам что нужно? Определить, какая функция быстрее растет что-ли? Это и без графиков видно (попробуйте прологарифмировать $\frac{f}{g}$)

[ewert]

ccoder в сообщении #418197 писал(а):

??

Всё очень просто. У Вас в первой строчке стоят какие-то таинственные значки. Естественно, никто их не понимает.

[ccoder]

У меня задание, такое
мне нужно найти являеться-ли $A = C(B)$, гже $C = O,o,\Omega ,\omega ,\Theta$
и поставить в таблице + или - соответственно.

-- Пн фев 28, 2011 14:58:50 --

Sonic86 в сообщении #418206 писал(а):

попробуйте прологарифмировать $\frac{f}{g}$

А как это делается?

[svv]

ccoder писал(а):

А как это делается?

Значит, Вы не очень хорошо понимаете, что значит $\log_2 n$ в формуле для $g(n)$?

[ccoder]

Я сам принцип пока что не уловил..

[Sonic86]

ccoder
Понимаете, сравнивать асимптотики двух элементарных функций - это очень просто, легче чем уравнения решать! Однако, если Вы не знаете, что такое логарифм и не работали с пределами - придется их изучить.
Что такое $C \in \{ O,o,\Omega ,\omega ,\Theta \}$ я надеюсь Вы знаете.
Вы можете сравнить асимптотики функций:
1. $x^a$ и $x^b$.
2. $P_n(x)$ и $Q_m(x)$, где $P_n, Q_m$ - многочлены степеней $n,m$?
3. $e^x$ и $x^n$ ($n$ - любое)?
4. $x^n$ и $\ln^m x$ ($n,m$ - любые)?
5. Сравнить $e^{f(x)}$ с $e^{g(x)}$ и $\ln f(x)$ с $\ln g(x)$, если можете сравнить $f(x)$ с $g(x)$?
для начала? Попробуйте сначала на эти вопросы ответить. И тогда сможете ответить и на свои вопросы.

[ewert]

Sonic86 в сообщении #418434 писал(а):

Что такое $C \in \{ O,o,\Omega ,\omega ,\Theta \}$ я надеюсь Вы знаете.

А вот я, кстати, не знаю, и даже знать не хочу. Т.е. что такое первые два значка -- знают все, а что такое остальные три -- практически никто. И это не случайно. Первые, в силу похожести на ноль -- ни для каких других целей (ну почти никаких) как обозначения не используются, последние же -- используются направо и налево и для каких угодно целей.

[Sonic86]

Цитата:

А вот я, кстати, не знаю, и даже знать не хочу. Т.е. что такое первые два значка -- знают все, а что такое остальные три -- практически никто. И это не случайно. Первые, в силу похожести на ноль -- ни для каких других целей (ну почти никаких) как обозначения не используются, последние же -- используются направо и налево и для каких угодно целей.

.
Скорее всего. Я вообще в основном $\sim, O$ и $\Theta$ использую (последнее обозначаю как $\sim\limits^{C}$).
Интересно - где он такие задания взял?
Но принцип действия все равно тот же будет.

[ccoder]

Извините что я долго не писал.

Я саму суть пока что ещё не уловил, может как-то ещё подсказать.
В моём примере я виже что можно привести к основанию $2$, тогда будет

Sonic86 в сообщении #418434 писал(а):

1. $x^a$ и $x^b$.

а что дальше делать?

[ccoder]

Если что-нибудь, что можно почитать?
Я что-то ненахожу совсем

[Sonic86]

Вы пределы считать умеете? матанализ у Вас в универе у Вас был?

-- Сб мар 05, 2011 20:38:36 --

Начните с определения $f(x) \sim g(x)$ при $x \to + \infty$. А затем решайте мои примеры по определению.
Можете посмотреть последнюю главу Кнута, Грэхема, Паташника в Конкретной математике

[ccoder]

Sonic86 в сообщении #419605 писал(а):

Вы пределы считать умеете? матанализ у Вас в универе у Вас был?

С этим у меня нормально.

Sonic86 в сообщении #419605 писал(а):

Начните с определения $f(x) \sim g(x)$ при $x \to + \infty$. А затем решайте мои примеры по определению.

Вот тут я непонимаю
Если они эквивалентны то

$$\[\mathop {\lim }\limits_{n \to + \infty } \frac{{f\left( n \right)}} {{g\left( n \right)}} = 1\]$$

что имеет вид тупика.

[Sonic86]

Ну почему же тупика. Это просто определение.
Мы сравниваем скорости роста функций $f,g$. Считаем, что далее все функции положительны с некоторого момента времени. Вам надо определить, верно ли $f = O(g)$ и верно ли $g = O(f)$ (м.б. и то и другое). В соотношение входит новый символ $O$. Что он значит? Он значит такое: $f(x) = O(g(x)) \Leftrightarrow (\exists C > 0)(\exists x_0)(\forall x) x > x_0 \Rightarrow f(x) \leq C g(x)$. Поскольку функции у нас обычно даны более-менее гладкие, то предел $\lim\limits_{x \to +\infty} \frac{g(x)}{f(x)}$ существует или равен $+\infty$. Поскольку предел существует или равен $+\infty$, то очевидно, что $f(x) = O(g(x)) \Leftrightarrow \lim\limits_{x \to +\infty} \frac{g(x)}{f(x)} \leq C$ - существует и конечен. Аналогично и разбирается соотношение $f(x) = O(g(x))$. Когда оба соотношения имеют место, то предел $C:0<C< + \infty$ Таким образом, мы не очень понятное (пока) соотношение с символом $O$ сводим к обычному пределу. Значит, остается найти предел. Если предел Вам кажется слишком сложным, начните с моих простых примеров.
Теперь давайте решать. Начнем с 1. Вам надо определить, $x^a = O(x^b)$ или нет. Вперед!