Доказательство того, что функция f(n) принадлежит Big-Theta(g(n))

Это упражнение, которое просит указать класс Big-Theta (g (n)) функции, к которому принадлежат, и доказать утверждение.

В этом случае f(n) = (n^2+1)^10

По определению f(n) E Big-Theta(g(n)) ‹=> c1*g(n) ‹ f(n) ‹ c2*g(n), где c1 и c2 — две константы.

Я знаю, что для этого конкретного f(n) Big-Theta есть g(n^20), но я не знаю, кто сможет это правильно доказать. Я думаю, мне нужно манипулировать этим неравенством, но я не знаю, как


inequality big-theta asymptotic-complexity
person PLS    schedule 27.04.2010    source источник
comment
Это домашнее задание? (если да, отметьте)   -  person Ming-Tang    schedule 27.04.2010

Ответы (2)


arrow_upward
2
arrow_downward

Функция f(x) есть (g(x)), если и только если:

  • f (x) равно O (g (x)), и
  • g(x) is O(f(x))

Итак, хотя вы могли бы попытаться доказать это с помощью одного неравенства, я предлагаю вам разбить его на эти две части; сначала докажите, что для некоторого n>n0 f(n) ‹ c1 g(n), а затем докажите, что для некоторого N › N0 g(N) ‹ c2 f(N). После того, как вы доказали обе части по отдельности, вы можете вернуться к определению, чтобы доказать, что f = (g).

person Michael Aaron Safyan    schedule 27.04.2010
comment
Вы имеете в виду, что * f (x) - это O (g (x)), а * g (x) - это Big-Omega (f (x)) ? Тем не менее я не могу найти способ работать, если f (n) для определения n0 и c1 или c2 - person PLS; 27.04.2010
comment
@PLS, нет, я имею в виду, что f - это большое-о-о, а g - это большое-о-о. Вам не нужно находить конкретные значения n0 или N0... это просто формальность, которая позволяет вам рассматривать только доминирующие члены. Вам также не нужно находить конкретные значения для c1 и c2, вам просто нужно показать, что член высшего порядка для обоих имеет одинаковую форму (чтобы вы могли легко выбрать c1 или c2, чтобы сделать это так, как вы хотите) . - person Michael Aaron Safyan; 27.04.2010
comment
ПОДСКАЗКА: если вы возьмете (n^2+1)^10, член ведущего порядка будет n^20. - person Michael Aaron Safyan; 27.04.2010
comment
Я это знаю, спасибо за помощь. Моя проблема в том, как манипулировать этими понятиями, чтобы доказать мое утверждение. - person PLS; 27.04.2010
comment
ПОДСКАЗКА: (n^2+1)^10 = n^20 + k n^18 + ... Найдите значение k, а затем вычислите значение n=n0, такое что kn^18 = n^20 .. , Для всех значений n больше n0 вы знаете, что (n ^ 2 + 1) ^ 10 ‹ 2n ^ 20 (поскольку член первого порядка равен n ^ 20, а член второго порядка ‹ n ^ 20). - person Michael Aaron Safyan; 27.04.2010

arrow_upward
0
arrow_downward

Я не очень разбираюсь в этом, но не могли бы вы доказать, что f(n) E Ο(n) и f(n) E Ω(n), а затем доказать, что f(n) E Θ(n) из-за определения пересечения?

person Michael M. Adkins    schedule 13.08.2010