Obtenha as melhores soluções para todas as suas perguntas no Sistersinspirit.ca, a plataforma de Q&A de confiança. Nossa plataforma de perguntas e respostas conecta você com especialistas prontos para fornecer informações precisas em diversas áreas do conhecimento. Obtenha soluções rápidas e confiáveis para suas perguntas de profissionais experientes 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]
Obrigado por usar nosso serviço. Estamos sempre aqui para fornecer respostas precisas e atualizadas para todas as suas perguntas. Sua visita é muito importante para nós. Não hesite em voltar para mais respostas confiáveis a qualquer pergunta que possa ter. Seu conhecimento é valioso. Volte ao Sistersinspirit.ca para obter mais respostas e informações.