Свойство О-большое

[Ward]

Здравствуйте!

Как строго показать, что если $f=O(O(\ln n))$, то $f=O(\ln n)$

[_hum_]

по определению

[arseniiv]

А запись $O(O(g))$ разве что-то означает?

[Ward]

Помогите пожалуйста!
Ну то, что $f=O(\ln n)$ означает, что $\dfrac{|f|}{\ln n}\leqslant C$
А что означает $f=O(O(\ln n))$?

[_hum_]

arseniiv в сообщении #710272 писал(а):

А запись $O(O(g))$ разве что-то означает?

Ну, $O(g)$, если не ошибаюсь, фактически означает некую функцию $u$, которая при достаточно больших значениях аргумента не превосходит (с точностью до мультипликативной константы) функцию $g$. Соответственно, $O(O(g)) = O(u)$ :)

[arseniiv]

Ward в сообщении #710273 писал(а):

$f=O(\ln n)$ означает, что $\dfrac{|f|}{\ln n}\leqslant C$

Не совсем (если квантор поставить ещё), кстати. Вот описание _hum_ полное.

Ward в сообщении #710273 писал(а):

А что означает $f=O(O(\ln n))$?

Оно могло бы означать $\exists g \mathbin. f = O(g) \wedge g = O(\ln n)$. Но лучше бы они так тогда и писали. Равенство в записях $f = O(g)$ — не то же самое, что обычное $=$ — это просто синтаксис, потому лично я не вижу ничего хорошего в путании записями вида $f = O(O(g))$.

-- Пн апр 15, 2013 02:05:55 --

Где-то видел обозначения вида $f\in O(g)$ — вот тут уже и $O(g)$ обозначает один конкретный объект — множество соответствующих функций.

[_hum_]

Whitaker, а там ситуация не такая же, как с классом эквивалентности и его представителем, когда в зависимости от контекста используется то один, то другой?

[Whitaker]

Вообще я знаю такое определение (почти всегда пользуюсь этим):

Цитата:

Пусть $f(x), g(x)$ - две функции, которые определены для достаточно большого положительного $x$, причем $f(x)$ - любая комплекснозначная функция, а $g(x)$ - положительная для достаточно больших $x$. Тогда соотношение $f(x)=O(g(x))$ при $x\to \infty$ означает, что для доcтаточно больших $x$ имеем $|f(x)|\leqslant Ag(x)$ при подходящем $A>0$

[arseniiv]

_hum_, мне вот тоже кажется.