Асимптотические порядки

Квас · ноября 4, 2011, 20:33

Престранно. Старенькая «шестёрка» даёт в первом случае тоже 0.

RawonaM · ноября 5, 2011, 09:17

Поэксперементировал: если стоит пробел, что между эн в квадрате и скобкой, то считает правильно, если пробела нет, то выдает бесконечность. В чем прикол?

arseniiv · ноября 5, 2011, 09:48

А вот в Mathematic'е я бы всегда смог посмотреть, как она это дело во внутренний вид распарсила! В Maple есть такая функция?

RawonaM · ноября 5, 2011, 10:05

Наверное есть, только я не знаю как.

Квас · ноября 5, 2011, 12:53

Пробел — знак умножения. Наверно, без пробела он интерпретировал n как имя функции.

Насчёт распаршивания я тоже не знаю.

RawonaM · ноября 5, 2011, 12:55

А что он делает с незнакомыми функциями? Почему он не говорит, что такая функция не определена? Он ее за 0 считает что ли?

Квас · ноября 5, 2011, 12:57

Цитата: RawonaM от ноября 5, 2011, 12:55
А что он делает с незнакомыми функциями? Почему он не говорит, что такая функция не определена? Он ее за 0 считает что ли?

Считает просто за n(), так же как a считает за некоторую величину. Если продифференцировать, например, то получится diff(n(x),x) — логично, собственно.

RawonaM · ноября 5, 2011, 13:01

Не понял. Откуда все-таки взялось ∞ в первом примере?

Квас · ноября 5, 2011, 13:03

Цитата: RawonaM от ноября 5, 2011, 13:01
Не понял. Откуда все-таки взялось ∞ в первом примере?

Бог его знает. Наверно, он решил, что поскольку числитель уходит в бесконечность, а о знаменателе он ничего сказать не может, то получается бесконечность.

RawonaM · ноября 5, 2011, 13:32

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

Квас · ноября 5, 2011, 13:59

Пересчитал: везде пределы получаются как надо.

RawonaM · ноября 5, 2011, 14:07

Спасибо

У вас тоже все вышли нули/бесконечности, т.е. все разных порядков?

Квас · ноября 5, 2011, 14:10

Ага, именно так.

RawonaM · ноября 5, 2011, 15:11

Почему-то в гуглдоксе 2 в степени корень логарифма выглядит как 2 умножить на корень.

RawonaM · ноября 19, 2011, 09:09

А если я для определения порядков беру обе стороны в 2^lg(x), порядки же должны сохраниться во всех случаях, неспа? Ведь это та же функция получается для х>0.
Допустим нужно определить f(n) ? g(n), берем в 2^{lg f(n)} ? 2^{lg g(n)}, если определяется отношение, то то же самое можно ставить между f(n) и g(n), верно?

RawonaM · ноября 19, 2011, 10:24

Мне нужно посчитать асимптотический порядок рекуррентного отношения
$[tex]T(n)=\sqrt n \cdot T(\sqrt n) + n \lg n[/tex]$

У меня получилось $[tex]\Theta(n \lg n)[/tex]$ , причем первая часть $[tex]\sqrt n \cdot T(\sqrt n)=\Theta(1)[/tex]$ , т.е. всегда константа. Может такое быть?

Квас · ноября 19, 2011, 13:47

Цитата: RawonaM от ноября 19, 2011, 09:09
Ведь это та же функция получается для х>0.
Допустим нужно определить f(n) ? g(n), берем в 2^{lg f(n)} ? 2^{lg g(n)}, если определяется отношение, то то же самое можно ставить между f(n) и g(n), верно?

Без сомнения, потому что написано одно и то же.

Квас · ноября 19, 2011, 13:55

Цитата: RawonaM от ноября 19, 2011, 10:24
Мне нужно посчитать асимптотический порядок рекуррентного отношения
$[tex]T(n)=\sqrt n \cdot T(\sqrt n) + n \lg n[/tex]$

А как вы делали? Пока я догадался только поделить на n lg n и получить соотношение между двумя дробями одинакового вида. Однако, кажется, ничто не мешает обеим уходить в бесконечность.

RawonaM · ноября 19, 2011, 14:18

Цитата: Квас от ноября 19, 2011, 13:55
Цитата: RawonaM от ноября 19, 2011, 10:24Мне нужно посчитать асимптотический порядок рекуррентного отношения
$[tex]T(n)=\sqrt n \cdot T(\sqrt n) + n \lg n[/tex]$
А как вы делали? Пока я догадался только поделить на n lg n и получить соотношение между двумя дробями одинакового вида. Однако, кажется, ничто не мешает обеим уходить в бесконечность.

Для уровня на один ниже верхнего:
$[tex]T(\sqrt n)=n^{1/4} \cdot T(n^{1/4}) + n^{1/2} \lg n^{1/2}[/tex]$

Отсюда $[tex]T(n)=n^{1/2}(n^{1/4} \cdot T(n^{1/4}) + n^{1/2} \lg n^{1/2}) + n \lg n[/tex]$ .
...
Для уровня i получается: $[tex]T(n)=\prod_{k=1}^i n^{1/2^k} \cdot T(n^{1/2^i}) + \sum_{k=0}^{i-1} n^{1/2^k} \lg n^{1/2^k}[/tex]$ .

Правое слагаемое $[tex]\Theta(n\lg n)[/tex]$ .

Левое слагаемое:
$[tex]\prod_{k=1}^i n^{1/2^k} \cdot T(n^{1/2^i})=n^{\sum_{k=1}^i 1/2^k} \cdot T(n^{1/2^i})[/tex]$

Определим T(2)=1, возьмем i=lg lg n (чтобы $[tex]n^{1/2^i}=2[/tex]$ ).

Подставим: $[tex]n^{\sum_{k=1}^i 1/2^k} \cdot T(n^{1/2^i})=n^{\sum_{k=1}^{\lg\lg n} 1/2^k}=n^{\frac{1-1/2^{\lg\lg n +1}}{1-1/2}}=n^{2-1/\lg n}=\frac{n^2}{n^{1/lg n}}[/tex]$
$[tex]=\frac{n^2}{2^{\lg n^{1/lg n}}}=\frac{n^2}{2}=\Theta(n^2)[/tex]$ .

Упс, вот и ошибка нашлась.

Значит все вместе $[tex]\Theta(n^2)[/tex]$ .

Квас · ноября 19, 2011, 14:31

Блин, высшая математика.

RawonaM · ноября 19, 2011, 14:31

Не, там еще одна ошибка в сумме.

Цитата: RawonaM от ноября 19, 2011, 14:18
Подставим: $[tex]n^{\sum_{k=1}^i 1/2^k} \cdot T(n^{1/2^i})=n^{\sum_{k=1}^{\lg\lg n} 1/2^k}=n^{\frac{1-1/2^{\lg\lg n +1}}{1-1/2}}=n^{2-1/\lg n}=\frac{n^2}{n^{1/lg n}}[/tex]$
$[tex]=\frac{n^2}{2^{\lg n^{1/lg n}}}=\frac{n^2}{2}=\Theta(n^2)[/tex]$ .

Должно быть:

$[tex]n^{\sum_{k=1}^i 1/2^k} \cdot T(n^{1/2^i})=n^{\sum_{k=1}^{\lg\lg n} 1/2^k}=n^{\sum_{k=0}^{\lg\lg n - 1} 1/2^{k+1}}=n^{1/2 \cdot \sum_{k=0}^{\lg\lg n - 1} 1/2^{k}}=[/tex]$

$[tex]=n^{1/2 \cdot \frac{1-1/2^{\lg\lg n}}{1-1/2}}=n^{1-1/\lg n}=\frac{n}{n^{1/\lg n}}=\frac{n}{2}=\Theta(n)[/tex]$ .

Опять таки выходит всего $[tex]\Theta(n \lg n)[/tex]$ .

RawonaM · ноября 19, 2011, 14:38

Цитата: Квас от ноября 19, 2011, 14:31
Блин, высшая математика.

Ага, не низшая точно

RawonaM · ноября 23, 2011, 23:10

$[tex]\Theta(\lg(n-1))[/tex]$ чему равно? Разве не $[tex]\Theta(\lg n)[/tex]$ ?
А то если раскрыть получится деление на ноль.

Квас · ноября 23, 2011, 23:17

Цитата: RawonaM от ноября 23, 2011, 23:10
А то если раскрыть получится деление на ноль.

Почему?

$[tex]\lg (n-1) = \lg n \cdot \frac{n-1}n = \lg n + \lg \left( 1-\frac 1n\right)[/tex]$

Последнее слагаемое стремится к 0, поэтому всё нормально.

RawonaM · ноября 23, 2011, 23:29

Ага, это я напутал. Спасибо

Лингвофорум

Асимптотические порядки

Квас

RawonaM

arseniiv

RawonaM

Квас

RawonaM

Квас

RawonaM

Квас

RawonaM

Квас

RawonaM

Квас

RawonaM

RawonaM

RawonaM

Квас

Квас

RawonaM

Квас

RawonaM

RawonaM

RawonaM

Квас

RawonaM

Быстрый ответ