Сравнение сложностей

Question

У меня есть три вопроса для обзора экзамена:

1. Если f(n) = 2n - 3 дать две разные функции g(n) а также h(n) (так g(n) не равно h(n)) такой что f(n) = O(g(n)) а также f(n) = O(h(n))
2. Теперь сделайте то же самое снова с функциями g'(n) а также h'(n), но на этот раз функция должна иметь видg'(n) = Ɵ(f(n)) а также f(n) = o(h'(n))
3. Это возможно для функции f(n) = O(g(n)) а также f(n) = Ω(g(n))?

Я знаю, что функция O(n) другого, если он меньше или равен другой функции. Поэтому я думаю, что 1. может быть g(n) = 2n²-3 а также h(n) = 2n²-10,

Я также знаю, что функция Ɵ(n) другой, если она в основном равна другой функции (мы можем игнорировать константы), и o(n) если это только меньше, чем функция, поэтому для 2. Я думаю, что вы могли бы иметь g'(n) = 2n-15 а также h'(n) = 2n,

К 3.: Функция может быть одновременно O(n) а также Ω(n) так как O(n) а также Ω(n) позволяет функции быть такой же, как данная функция, так что вы можете иметь функцию g(n) это равно f(n) и удовлетворяет правилам как O а также Ω,

Может кто-нибудь сказать мне, если это правильно?

Answer 1

Ваши ответы в основном правильные. Но я хотел бы добавить несколько моментов:

Дано f(n) = 2n - 3

1. С g(n) = 2n²-3 а также h(n) = 2n²-10f(n) в O(g(n)) И в O(h(n)), Но ваши g (n) и h (n) в основном одинаковы, по крайней мере, они оба в Θ(n²), Существует много других функций, которые также будут работать. Например

   • f(n) ∈ O(n) ⇒ g(n) = n
   • f(n) ∈ O(nk) ⇒ g(n) = nk ∀ k ≥ 1
   • f(n) ∈ O(2ⁿ) ⇒ g(n) = 2ⁿ

2. g'(n) = 2n-15 сводится к g'(n) = n, если мы думаем в сложностях, и это правильно. На самом деле, это единственный возможный ответ.
   Но f(n) ∈ o(h'(n)) не держится за h'(n) = 2n, Little-o означает, что

   limn → ∞ | f (n) / g (n) | = 0 ⇔ f (n) ∈ o (g (n))

   Так что вы можете выбрать h'(n) = n² или более общий h'(n) = nk ∀ k > 1 или же h'(n) = cⁿ для постоянного c > 1,

3. Да, это возможно, и вы можете принять это также в качестве определения для Θ(g(n)):

   f (n) ∈ Θ (g (n)) ⇔f (n) ∈ O (g (n)) и f(n) ∈ Ω(g(n))