8
respostas

Algoritmo e Matemática

Ainda não consegui relacionar matemática e programação em alguns casos. O Big o notation serve para verificar velocidade de processamento de código, mas não consegui entender as nomenclaturas e saber quando o algoritmo é lento ou rápido.

E algumas resoluções, porque sem tem que saber o resto dá divisão, esses são dois exemplos, se o número primo é divisível somente por um e ele mesmo, porque começa com 2:

```function primeFactors(n){ var factors = [], divisor = 2;

while(n>2){ if(n % divisor == 0){ factors.push(divisor); n= n/ divisor; } else{ divisor++; } } return factors; }

primeFactors(69); = [3, 23]


function greatestCommonDivisor(a, b){ if(b == 0) return a; else return greatestCommonDivisor(b, a%b); } ```

8 respostas

Boa tarde Gisele,

de quais nomenclaturas você está falando? Não consegui entender esse ponto da pergunta.

Quanto à verificação do resto da conta isso serve para você saber se um número é divisível por outro, por exemplo 4/2,o reto é 0 agora 3/2 o resto é 5.

Obs.: teve uma pequena falha na formatação do código, se você puder editar ajudaria :)

Oi, obrigada.

nomenclaturas:

Θ(lgn) Θ(1) Θ(lgn)

Se um tempo de execução é O(f(n)), então para um n suficientemente grande , o tempo de execução é no máximo k⋅f(n) para alguma constante k . Veja como pensar em um tempo de execução que é O(f(n)).

Eu estudei gráfico no 2º grau, mas já terminei faz tempo, então eu esqueci algumas coisas de gráfico e nessa explicação não ficou muito claro.

Assisti a aula aqui da Alura, mas não explica o porque de utilizar essas expressões matemáticas.

Fonte: https://pt.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation

Não entendi, porque a prioridade de b ser igual a 0, porque checa primeiro se b é igual a 0 e no retorno recursivo, retorna b e o resto de a / b.

function greatestCommonDivisor(a, b){ if(b == 0) return a; else return greatestCommonDivisor(b, a%b); }

Esse eu fiquei pensando que no exercício fala que o número primo é divisível por ele mesmo e por 1, para descobrir isso é só saber se o resto é 0?

function primeFactors(n){ var factors = [], divisor = 2;
while(n>2){ if(n % divisor == 0){ factors.push(divisor); n= n/ divisor; } else{ divisor++; } } return factors; }
primeFactors(69); = [3, 23]

Bom dia Gisele,

Acredito que sua dúvida nem é em relação ao código em si, e sim mais o entendimento de como o Big O Notation funciona, te recomendo ler um pouco sobre ele: https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity

Confesso que li bem por cima, mas me pareceu ser uma boa explicação de como funciona e tem exemplos também.

Quem sabe dá uma ajuda no seu entendimento.

Abraço.

Oi Gisele, o link passado pelo Emerson é realmente bem interessante, mas acho que inicialmente você nem precisa se preocupar muito com isso, você pode começar a estudar algoritmos de busca ou de ordenação, para entender como funciona, esse lado do Big O Notation seria mais interessante caso você já tenha visto um básico de algoritmos é gostaria de estudar com mais detalhes a análise de algoritmos, estudando linha por linha para saber o tempo de execução e prever gargalo para poder melhorar.

Eu recomendo você iniciar com os algoritmos que temos aqui na Alura, pode ir estudar o livro do Guilherme Silveira, e também recomendo o livro Desmistificando Algoritmos que é um livro mais intermediário, e depois, caso você queira ir bem à fundo nisso (e ter uma certa grana disponível) pode ler o livro Algoritmos. Teoria e Prática esse é bem interessante, mas caro, e esses dois últimos livros que citei não tratam de uma linguagem em específico, eles tratam de algoritmos, puramente algoritmos.

Espero ter ajudado e não te desanimado :)

Obrigada. As duas respostas se completam, vou ler o link com calma e eu comprei uns livros de algoritmos, inclusive esse desmistificando que eu achei melhor ler um mais básico primeiro.

Estou lendo esse:

https://www.amazon.com.br/Estrutura-Dados-e-T%C3%A9cnicas-Programa%C3%A7%C3%A3o/dp/8535274375/ref=sr_1_fkmr0_3?ie=UTF8&qid=1490637639&sr=8-3-fkmr0&keywords=estrutura+de+dados+e+seus+algoritmos

O problema é que eu fui aprendendo por demanda, o que precisava eu aprendia e acabei não estudando tanto a parte teórica.

Eu vi na Khan Academy essa parte de busca binária e dividir o array pela metade para ser mais rápido do que um por um.

Mas esses de múltiplos e cálculos é que eram minha dúvida porque sempre calcula o resto da divisão. Quando você aprende o MMC na matemática acaba seguindo um racicionio diferente, porque você tem os números e é mais fácil saber qual é divisivel por 2, 3... Na programação você não tem esses dados de qual é o número, não tem como bater o olho e dar a resposta. Não sei se eu consegui explicar direito.

Ainda fiquei sem entender o GCD, esse tipo de solução, primeiro checa se b é igual a 0, porque checa primeiro se b é igual a 0 e no retorno recursivo, retorna b e o resto de a / b. Em português equivale a Máximo Divisor Comum?

Gisele é isso ai, GCD é igual ao MDC mesmo.

Exatamente a mesma coisa, somente muda que um está em português e o outro em inglês.

Agora eu entendi melhor o MDC, na escola eu aprendi a calcular de um jeito que era começando a dividir pelo menor número, que poderia ser 2 ou 3:

https://matematicabasica.net/mdc-maximo-divisor-comum/

Mas pesquisando na internet, achei a explicação que fez todo sentido, acontece que essa solução de algoritmo, é baseada no algoritmo de Euclides, uma outra forma de calcular o MDC:

function greatestCommonDivisor(a, b){
     if(b == 0) return a; 
    else 
    return greatestCommonDivisor(b, a%b);
 }

Essa explicação me ajudou a entender:

http://clubes.obmep.org.br/blog/sala-de-estudos-algoritmo-de-euclides-para-determinacao-de-mdc/

Muitos livros sobre o assunto só colocam as soluções e as formulas, mas não explicam porque utilizam determinada formula ou solução, por isso fica mais dificil, na escola mesmo era mais decorar formulas do que entender para que serve aquela formula...