Я полагаю, что вопрос просит вас доказать или опровергнуть утверждение. Когда речь заходит об асимптотической записи c, использующей символы меньше / равно / больше чем, это может сбить с толку новых учеников, потому что это в некотором роде подразумевает уравнение между двумя, когда на самом деле оно говорит совершенно другое.
O (g (n)) на самом деле набор функций, который ограничен сверху g (n) кратным некоторому постоянному коэффициенту для достаточно большого п . В математике вы бы сказали: f (n) ≤ O (g (n)) означает f (n) ≤ c g (n) для c> 0, n> N . Именно поэтому ≤ используется для O. Big-Omega определяется аналогично, но как нижняя граница. Есть много функций, которые могут удовлетворять верхней и нижней границам, что является причиной, по которой он определяется как набор.
Так что для этого может быть более понятно использовать наборную нотацию. Вы можете express то же самое, что и:
f(n) ∈ O(g(n))
f(n) ∈ Ω(g(n))
Так что f (n) ≤ O (g (n)) означает то же самое, что и f (n) = O (g (n)) , что совпадает с f (n) ∈ O (g (n)) . И f (n) ≥ Ω (g (n)) означает то же, что f (n) = Ω (g (n)) , что совпадает с f (n) ∈ Ω (g (n)) .
Так что на самом деле вас просят доказать, можете ли вы иметь функцию f (n) , которая ограничена сверху и ниже на г (н) .
Можно. Это на самом деле определение для Big-Theta. Ө (g (n)) - это набор всех функций, так что g (n) является асимптотикой c верхней и нижней границы этих функций. Другими словами, h (n) = Ө (g (n)) подразумевает c₁ g (n) ≤ h (n) ≤ c₂ g (n) для достаточно больших n .
Если f (n) = 7n ^ 2 + 500 , тогда подходящая верхняя и нижняя граница может составлять n ^ 2 , поскольку f (n) ≥ 1 * n ^ 2 и f (n) ≤ 8 * n ^ 2 для всех n> 10 . Поэтому f (n) ∈ Ө (n ^ 2) .