Можно ли показать, что f(n)/log(n) = O(g(n)) => g(n) = Θ(f(n))?f (n)/log (n) = O (g (n)) ⇒ g (n) = Θ (f (n))?
Прямо сейчас я стою здесь:
f(n)/log(n) = O(g(n)) ⇒ f(n)/log(n) ≤ c₁⋅g(n) ⇒ f(n)/(c₁⋅log(n)) ≤ g(n)
g(n) = Θ(f(n)) ⇒ c₂⋅f(n) ≤ g(n) ≤ c₃⋅f(n)
Тогда я говорю: c₂ = 1/(c₁⋅log(n)) ⇒ c₂⋅f(n) ≤ g(n)
Если это правильно, как я показать верхнюю границу?
Нет, это не близко к истине. Есть две проблемы. Во-первых, отношения Тэта связаны как с верхней, так и с нижней границей, но (как вы заметили) вы только предполагаете, что g дает верхнюю границу по f. Так, например, попробуйте f (n) = 0 и g (n) = n: предположение верно, но вывод ложный. Во-вторых, коэффициент log (n) не является постоянным фактором, что также мешает вам установить плотную связь между f и g; например, см. комментарий от @templatetypedef.
Как было сказано ранее, вы можете опровержение предположения с (общим), например:
Пусть f(n) = g(n) ⋅ log(n), то f(n)/log(n) ∈ O(g(n)) держится, но, очевидно, g(n) ∉ Θ(f(n)).
То, что вы можете показать это:
f(n)/h(n) ∈ Θ(g(n)) ⇒ g(n) ∈ Θ(f(n)/h(n)) ⇒ g(n) ∈ O(f(n))
Как намек, что, если е (п) = п п и войти г (п) = п? – templatetypedef
Это вопрос кода? – CompanyDroneFromSector7G
@templatetypedef это само собой разумеется. Но как я могу показать, что это выражение применимо к любым двум функциям? – sashqaqq