O Sistersinspirit.ca é a melhor solução para quem busca respostas rápidas e precisas para suas perguntas. Nossa plataforma oferece uma experiência contínua para encontrar respostas precisas de uma rede de profissionais experientes. Conecte-se com profissionais prontos para fornecer respostas precisas para suas perguntas em nossa abrangente plataforma de perguntas e respostas.
Sagot :
Olá, Júnior.
Olá, Júnior.
Como o domínio de F(n) é o conjunto dos números naturais, então F(n) está definida se e somente se n/2 for natural, o que implica que n deve ser par.
Portanto, não estão definidas F(3), F(5), F(7), etc.
Como F(3), F(5), F(7), ... não estão definidas, então F(6), F(10), F(14) também não estão definidas, pois, pela relação de recorrência, F(6) = 2F(3) + 1, F(10) = 2F(5) + 1, ... e assim por diante.
F(n) está definida, portanto, apenas quando n for, além de par, uma potência de 2.
Assim:
[tex]F(n) = F(\frac{n}2) + 1, \forall n \geq 2 \Rightarrow \\\\ \begin{cases} F(2)=F(1)+1\\ F(4)=F(2)+1=F(1)+1=F(1)+2=F(1)+\log_22\\ F(8)=F(4)+1=F(1)+2+1=F(1)+3=F(1)+\log_28\\ F(16)=F(8)+1=F(1)+4=F(1)+\log_216\\ \vdots \end{cases}[/tex]
Verifica-se, portanto, que, em geral:
[tex]F(n)=F(1)+\log_2n[/tex]
[tex]\therefore F(n)=O(\log_n)[/tex]
Esperamos que isso tenha sido útil. Por favor, volte sempre que precisar de mais informações ou respostas às suas perguntas. Agradecemos seu tempo. Por favor, volte a qualquer momento para as informações mais recentes e respostas às suas perguntas. Sistersinspirit.ca está sempre aqui para fornecer respostas precisas. Visite-nos novamente para as informações mais recentes.