Como faço para comprovar que US $ 3x ^ 3 + 2x + 1 $ é $ \ ÔMGA (x \ Cdot \ Log x) $

Question

Eu estou tentando responder a essa pergunta: $ 3x ^ 3 + 2x + 1 $ é $ \ ômega (x \ cdot \ log x) $

minha pergunta é como resolver esta questão.

Aqui está o que eu tentei até agora:

Eu apliquei a definição $ 3x ^ 3 + 2x + 1> c \ cdot x \ log x $ para todos os c, dado $ n \ geq k $ , para alguns k

Eu tentei aplicar a técnica de aplicar a igualdade que: $ n

Como n é menor do que o termo de ordem mais alta que podemos simplesmente mover todos os termos para encomendar n ??

dar $ 6x

Então você pode escolher: $ k <2 ^ \ frac {6} {c} $

Answer 1

O que eu recomendo primeiro é notar que, se você está olhando para a complexidade da função $ 3x ^ 2 + 2x + 1 $ , Realmente tudo o que você deve se importar é a função $ x ^ 2 $ . Porque se você vai provar que $ x ^ 2= ímã (xlogx) $ Em seguida, adicionando a $ 2x + 1 $ Não arruinará essa prova desde a $ x ^ 2 $ é polinomialmente maior que $ 2x + 1 $ e para que possamos apenas olhar para a $ x ^ 2 $ . < / p >.

(eu vou usar $ n $ em vez de $ x $ porque é isso que eu sou familiarizado, mas é exatamente o mesmo para $ x $ )

Então agora o que queremos provar é que $$ n ^ 2= ômega (nlogn) $$

Qual como você oferecia apenas você precisa virar os lados na equação, precisaremos encontrar uma $ c $ , de modo que para qualquer $ n> n_0 $ ou $ n> k $ : $$ f (n) \ ge c \ cdot g (n) $$ quando $ f (n)= n ^ 2 $ , $ g (n)= nlogn $

Isso nos levará a: $ n ^ 2 \ ge cnlogn $

Podemos dividir ambos os lados por $ n $ : $$ n \ GE clogn $$

Agora isso é um pouco complicado. mas "é conhecido" que o tempo de execução polinomial é mais lento que o logarítmico.

Basicamente o que isso significa é que você preferiria atingir uma complexidade logarítmica em execução, se possível, porque você obterá uma execução mais rápida.

Geralmente esta é a ordem de horários em execução quando o primeiro é o mais rápido:

$$ 1.Constant $$ $$ 2.Logaritmic $$ $$ 3.Linear $$ $$ 4.Linearithmic $$ $$ 5.Polynomial $$ $$ 6.Exponencial $$

(você pode ler mais sobre isso aqui: https://adrianmejia.com/most-popular-sgorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course/ ) .

Outra maneira de ver é se você encontrar o limite da divisão das duas funções, digamos que escolheremos: $$ {f (n) \ sobre g (n)} $$

se $$ \ lim_ {n \ to fraty} {f (n) \ over g (n)} \ righttarrow \ infty $$ Isso significa que $ f (n) $ é "muito maior" do que $ g (n) $ < / p >.

Se $$ \ lim_ {n \ to infty} {f (n) \ sobre g (n)} \ righttarrow 0 $$ Isso significa que $ f (n) $ é "muito menor" do que $ g (n) $ < / p >.

A última opção (pelo menos neste método) é: $$ \ lim_ {n \ to infty} {f (n) \ sobre g (n)} \ rightarrow c $$ Quando $ c \ gt 0 $ O que significa que ambas as funções têm assintoticamente a mesma complexidade.

De volta às nossas funções, podemos ver que: $$ \ lim_ {n \ to fraty} {n \ sobre log (n)} $$

Vamos usar a regra lupital e obter: $$ \ lim_ {n \ to infty} {1 \ mais de 1 / n} \ righttarrow \ frty $$

Agora podemos ver que $ f (n)= n $ é maior assintoticamente de $ g (n)= log (n) $ portanto: $$ n= Ômega (log (n)) $$

---

.

Eu realmente espero explicar o mais claro e fácil possível, é apenas o inglês não é minha língua materna língua, então eu apolegio com antecedência por qualquer erro com a gramática etc.

---

.

Atualização: Eu notei que você fez alterações na função original e agora é $ 3x ^ 3 + 2x + 1 $ , mas a prova Seja o mesmo, basta usar $ n ^ 3 $ e do que você ainda obterá o mesmo resultado ao usar o Lupital. Que, inevitavelmente, se acabamos de provar que $ n ^ 2 $ é muito maior do que $ log (n) $ < / span> do que é claro que $ n ^ 3 $ que é muito maior do que $ n ^ 2 $ também seria maior que $ log (n). $

Answer 2

A maneira mais fácil é verificar se $ \ lim_ {x \ to \ infty} \ frac {3x ^ 3 + 2x +1} {x \ log x}= + \$ , que é uma condição suficiente para $ 3x ^ 3 + 2x +1 \ in \ omeega (x \ log x) $ .

$$ \ lim_ {x \ to \ infty} \ frac {3x ^ 3 + 2x +1} {x \ log x}= \ lim_ {x \ to \ infty} \ frac {3x ^ 3} {x \ log x}= \ lim_ {x \ to \ infty} \ frac {3x ^ 2} {\ log x}= \ lim_ {x \ to \ infty} 6x ^ 2 = + \ infty. $$