Алгоритмы и структуры данных?

Question

[Rustam2002]

Почему функция g(n) не может быть асимптотически положительной, ведь даже если она будет такой функция f(n) входит в множество

Comments

[Модератор]

Следующий вопрос, которому вы не потрудитесь дать нормальный заголовок, будет удалён.

Answer 1

[Mercury13]

Если f(n) ≡ 0 (неотрицальна → асимптотически неотрицательна), то вполне срабатывает, что 0=Θ(0).
То есть по нашему определению множества Θ, если оно непустое, то g обязана быть асимптотически неотрицательной — но не обязательно асимптотически положительной.

Comments

[Rustam2002]

Извините, не очень понятно. Можете пожалуйста попроще объяснить и с примерами, если можно?

[Mercury13]

Rustam2002,
Я написал. Не «не может быть», а «может не быть», и достаточно найти контрпример, где она не является асимптотически положительной.
И этот контрпример простой: f и g — функции, всегда равные нулю.

[Rustam2002]

Mercury13, но функция g(n) может быть и асимптотически положительной и она будет непустой при этом?

[Rustam2002]

Rustam2002, здравствуйте

[Mercury13]

Rustam2002, Если функция g(n) асимптотически положительна, то её Θ(g) состоит из одних асимптотически положительных функций, это понятно.

[Rustam2002]

Mercury13, да, понятно

[Rustam2002]

То есть она может быть асимптотически положительной и при этом не пустой

[Mercury13]

Rustam2002, Пустая функция — нет такого понятия.
У любой асимптотически неотрицательной функции множество Θ непустое.
Потому что как минимум включает её саму.

[Mercury13]

Rustam2002, Символы Θ и Ω, НЯЗ, придумал Дональд Кнут на основе известных из муть-анализа символов Ландау. Но чтобы «подпереть» функцию снизу, потребовалась неотрицательность.

[Mercury13]

Rustam2002, И дальше включается думалка: а какой вариант самый общий? А может функция иметь немного отрицательных точек? А где она может иметь нули?

Answer 2

[Михаил Ливач]

поскольку f(n) асимптотически неотрицательна, то есть хотя бы иногда образается в ноль, то g(n) не может быть асимптотически положительной, так как ей необходимо ограничивать f(n) снизу: c*g(n) ≤ f(n).
Для примера можно взять функцию sin(x)+1

Answer 3

[code_panik]

Любая функция является своей точной асимптотической оценкой (как O-большое, так Ω-большое), поэтому в общем случае множество не пусто. Просто перечитайте аккуратно определение из книги на предыдущей странице. Там все константы положительные и все рассматриваемые функции асимптотически неотрицательные. Асимптотически положительная функция является асимптотически неотрицательной.