Сложность времени Литтл-ом и Литл-Омега

Question

Из того, что я знаю, у little-oh должен быть предел n, приближающийся к бесконечности (function / little-oh, omega function), который = 0, а для маленьких omega предел должен равняться бесконечности.Тем не менее, возможно ли наличие нескольких маленьких омов и маленьких омег, которые бы сделали предел истинным?

То есть, возможно, что есть много маленьких омов и маленьких омег, которые подойдутодно уравнение?

Answer 1

Да.Little-o - это своего рода верхняя граница, а little-omega - это своего рода нижняя граница.В общем, любая верхняя граница для известной верхней границы сама является верхней границей.И также любая нижняя граница известной нижней границы сама является нижней границей.Таким образом, всегда есть бесконечно много верхних границ и обычно бесконечно много нижних границ.

Причина "обычно" среди нижних границ заключается в том, что 0 не имеет нижних границ среди неотрицательных функций и, как правило, во времени.сложности вы никогда не найдете ничего, что мало омега константы.Но если f(n) уходит в бесконечность, то у вас есть log(f(n)), log(log(f(n)), log(log(log(f(n))), ... для бесконечного ряда нижних границ.

Что касается верхних границ, то это "всегда «потому что вы можете умножить любую положительную функцию на n, n^2, n^3, ..., чтобы получить бесконечное число строго больших верхних границ.