Fórum de Matemática | DÚVIDAS? Nós respondemos! https://forumdematematica.org/ |
|
Algebra para analise de algoritmo. https://forumdematematica.org/viewtopic.php?f=13&t=14107 |
Página 1 de 1 |
Autor: | mjf2004 [ 29 jan 2019, 15:38 ] |
Título da Pergunta: | Algebra para analise de algoritmo. |
Depois de analisar um algoritmo, consegui chegar nessa expressão abaixo, porém não consegui desenvolver a partir daí. Consegui o gabarito com outra turma da faculdade, mas queria entender como foi realizado tal operação. Alguém poderia me explicar como a expressão algebrica abaixo.... T(n) = n(n-1)+(n-1)+(n-2)+....3.2+2.1+1.0 Resultou nessa resposta: T(n) = c*n³ ---- n Que operações matetmaticas foi utilizada? |
Autor: | Rui Carpentier [ 30 jan 2019, 15:37 ] |
Título da Pergunta: | Re: Algebra para analise de algoritmo. [resolvida] |
\(T(n)=n(n-1)+(n-1)(n-2)+\cdots + 3\cdot 2+2\cdot 1 +1\cdot 0=\) \(= 2\left(\frac{n(n-1)}{2}+\frac{(n-1)(n-2)}{2}+\cdots + \frac{3\cdot 2}{2}+\frac{2\cdot 1}{2}+\frac{1\cdot 0}{2}\right) =\) \(= 2\left({n \choose 2}+{n-1 \choose 2}+\cdots +{3 \choose 2}+{2 \choose 2}+{1 \choose 2}\right)\). Pela identidade de stick de hockey, temos que \({n \choose 2}+{n-1 \choose 2}+\cdots +{3 \choose 2}+{2 \choose 2}+{1 \choose 2} = {n+1 \choose 3}\), logo \(T(n)=2{n+1 \choose 3} = \frac{n^3-n}{3}\). |
Autor: | mjf2004 [ 01 fev 2019, 20:37 ] |
Título da Pergunta: | Re: Algebra para analise de algoritmo. |
Obrigado!! Agora falando com um amigo, eu preciso dos fundamentos de indução matematica e soma dos quadrados. Por isso eu não enxergava uma saída para as operações. Alguma dica para adquirir essas habilidades, ja estou assistindo video aulas a respeito. |
Página 1 de 1 | Os Horários são TMG [ DST ] |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |