What does this o-notation mean?

[Bars]

В англоязычной статье/стр. 3 встретилось обозначение $K(t) \in t^{o(1)}$. Что так обычно обозначают в англоязычных статьях? В идеале хотелось бы увидеть в качестве ответа предикат с кванторами, потому, что вещи типа $K(t) = O(t^o(1))$ я тоже не понимаю. А предикат с кванторами пойму. Спасибо.

[Munin]

Вот это смотрели? http://en.wikipedia.org/wiki/Big_O_nota ... o_notation

[Bars]

Да, смотрел. Там везде справа от знака $\in$ стоит $o(...)$, а под знаком $o$ стоит функция. В моём случае - по-другому. Никто не может объяснить, что это. А сам я не могу на интуитивном уровне понять.

[Someone]

Рискну предположить, что $o(1)$ означает функцию, предел которой равен $0$.

[EtCetera]

Bars в сообщении #624081 писал(а):

Там везде справа от знака $\in$ стоит $o(...)$, а под знаком $o$ стоит функция.

Да нет. В разделе Little-o notation написано буквально следующее:

Цитата:

...the relation $f(x) = o(g(x))$ is equivalent to

$$\lim_{x \to \infty}\frac{f(x)}{g(x)}=0.$$

For example,

• $2x \in o(x^2)$
• $2x^2 \not \in o(x^2)$
• $1/x \in o(1)$

При $g(x)=1$ имеем $\lim\limits_{x \to \infty}f(x)=0$, т.е. Someone прав.

[Munin]

Bars в сообщении #624081 писал(а):

Там везде справа от знака $\in$ стоит $o(...)$, а под знаком $o$ стоит функция.

Не везде. Выше даны примеры и пояснения, когда o-обозначение используется внутри выражения - http://en.wikipedia.org/wiki/Big_O_nota ... f_notation

[Bars]

При $g(x)=1$ имеем $f(x) \in o(1)$, я знаю, что это значит. И здесь опять после знака $\in$ стоит $o(g(x))$, всё в порядке.
А в обозначении $F(t) \in 1^{o(1)}$, о котором я спрашиваю, после знака $\in$ стоит выражение $1^{o(1)}$, а не $o(g(t))$. Я не понимаю, что это значит.

[Someone]

Дык, $g(t)=1$ для всех $t$.
А обозначение $1^{o(1)}$, боюсь, без автора этого обозначения мы не расшифруем. Может быть, он под $1$ в основании степени подразумевает функции, стремящиеся к единице, но это только попытка угадать.

[ИСН]

Справа от знака $\in$ обычно стоит какое-то множество. Значит, $o(1)$ в выражении $f(x) \in o(1)$ - это какое-то множество. Согласны? Какое?

[Munin]

Bars в сообщении #624118 писал(а):

Я не понимаю, что это значит.

Ну так дочитайте, там есть выражения типа $n^{O(1)},$ аналогичные тому, что вас интересует, и подробно про них рассказано.

[Cash]

Bars в сообщении #624118 писал(а):

При $g(x)=1$ имеем $f(x) \in o(1)$, я знаю, что это значит. И здесь опять после знака $\in$ стоит $o(g(x))$, всё в порядке.
А в обозначении $F(t) \in 1^{o(1)}$, о котором я спрашиваю, после знака $\in$ стоит выражение $1^{o(1)}$, а не $o(g(t))$. Я не понимаю, что это значит.

$1^{o(1)}$ - это явная чушь и, к счастью, в статье этого нет.
Речь идет о $t^{o(1)}$.
Это класс функций которые возрастают медленнее любой степенной, например, логарифмическая.
$K(t) \in t^{o(1)} \Longleftrightarrow \forall \varepsilon>0 \quad \lim_{t \to \infty}\frac{K(t)}{t^{\varepsilon}}=0$

[RIP]

Cash в сообщении #624160 писал(а):

Речь идет о $t^{o(1)}$.
Это класс функций которые возрастают медленнее любой степенной, например, логарифмическая.
$K(t) \in t^{o(1)} \Longleftrightarrow \forall \varepsilon>0 \quad \lim_{t \to \infty}\frac{K(t)}{t^{\varepsilon}}=0$

Это неверно: возьмите, например, $K(t)=t^{-1}$. То есть там стрелочка только слева направо. А $t^{o(1)}$ — это класс функций вида $t^{\varepsilon(t)}$, где $\varepsilon(t)=o(1)$.

[Cash]

Вы правы, по тексту подразумеваются неограниченно возрастающие, но медленнее степенной. Ограниченные и убывающие своей записью не отсек
Наверное, так?

$$K(t) \in t^{o(1)} \Longleftrightarrow \forall \varepsilon>0 \quad \lim_{t \to \infty}\frac{K(t)}{t^{\varepsilon}}=0, \quad \lim_{t \to \infty}K(t)= \infty$$

Или константы тоже в класс $t^{o(1)}$ включены?

[Bars]

Получается, $K(t)\in t^{o(1)}$ - это сокращение для $K(t)\in o(t^{o(1)})$, а последнее - сокращенная запись для $K(t)\in o(t^{g(t)})$, где $g(t)\in o(1)$? Если да, то как на счет независимости от выбора $g(t)\in o(1)$...

[ИСН]

ИСН в сообщении #624140 писал(а):

Справа от знака $\in$ обычно стоит какое-то множество. Значит, $o(1)$ в выражении $f(x) \in o(1)$ - это какое-то множество. Согласны? Какое?