Big Oh обозначение (как написать предложение)

Question

У меня был тест на асимптотику, и возник вопрос:

Обратите внимание на следующее:

O (o (f (n)) = o (f (n))

1. Напишите в словах значение утверждения, используя условные обозначения из асимптотической нотации.
2. Это утверждение верно или ложно? Обоснуйте.

Я ошибся (не помню точно, что я написал), но я думаю, что-то вроде:

Для любой функции g (n) = o (f (n)) является функцией h (n) = o (f (n)), так что h (n) = O (f (n)).

Это правильно?

И для (2) я не совсем уверен. Может ли кто-нибудь помочь мне с этим тоже?

Заранее спасибо.

Answer 1

Я думаю, что они пытались задать вопрос о взаимосвязи между Big O и асимптотическими обозначениями little o.

A) Граница Big O для ограниченной функции Little O уменьшает / подразумевает границу Little O дляэта функция.

B) Верно.Большая O является менее «строгой» границей, поскольку она предусматривает наличие M и x0 таких, что f (n) <= M * g (n) для x> = x0, тогда как Little O оговаривает, что для всех положительных M, существует такое x0, что f (n) ограничено сверху M * g (n).

Таким образом, "M" большого O является подмножеством "всего M" маленького Oи, таким образом, O (o (f (n)) эквивалентно o (f (n)).

Фактическую математику, а не мою слабую аську, смотрите на странице википедии

Answer 2

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

То, как обычно преподаются нотации big-O (особенно на уроках информатики), заключается в том, что O (f (n)) - это функция. Это должно отключить некоторые сигналы тревоги, так как операторы «n = O (n)» и «2n = O (n)» оба являются истинными, а «n = 2n» - нет. Если мы хотим сказать «f (n) - это big-O of g (n)», технически мы не должны говорить «f (n) = O (g (n))», скорее мы должны сказать «f (n) ) является элементом O (g (n)) ". Первый - это просто удобная стенография.

Итак, возвращаясь к актуальному вопросу, O (o (f (n))) не очень много значит (или, по крайней мере, я никогда не видел формального определения big-O для набора функций). , Но я предполагаю, что логичный способ интерпретации этого был бы в соответствии с ответом Enjay, с g (n) = o (f (n)).

Answer 3

Значение на простом английском языке: верхняя граница функции, которая строго больше, чем f (n), строго больше, чем f (n). Ваше утверждение могло быть записано как: Для любой функции g (n) = o (f(n)) существует h (n) = O (g (n)), из чего следует, что h (n) также o (f (n)) => O (g (n)) = o (f (n))=> O (o (f (n))) = o (f (n)) Да, утверждение верно.(конечно, вышеприведенное утверждение предполагает наличие всех правильных констант, и использование «строго больше - это удобочитаемость и понимание: оно должно быть« строгим верхним пределом »)