Eficiência algorítmica

RKA13C Agora eu tenho um relatório de que enviarão o novo rover à Marte. Nós somos responsáveis por fazer uma coisa que está programando o algoritmo dentro do rover, que verifica se os números são primos. Digamos que o nosso rover está se comunicando usando RSA. Ele precisa de um algoritmo dentro que possa fazer um teste de primalidade. Quando você cria um rover ou qualquer coisa para ir ao espaço, você tem que ser muito eficiente em todos os sentidos. Os componentes utilizados devem ser muito leves, a quantidade de energia que todos os subsistemas usam tem que ser mínima. Você tem que economizar energia e massa em todos os pontos do processo de design. Então, nosso trabalho é o seguinte: temos que ser capazes de lidar com números deste tamanho e temos que fazer isso muito rapidamente. Se nós dermos uma pequena entrada, digamos que de apenas 90, ele deve ser capaz de calcular quase tão rapidamente como este número inteiro. Conforme a entrada cresce, não queremos que haja uma diminuição perceptível. Eu quero analisar as perguntas dos usuários ou as ideias que eles têm que foram realmente boas de um ponto de vista matemático. Estamos verificando se "n" é primo composto. Dado o número "n", pense neste espaço de todos os "n" possíveis. Se "n" for 100, esse espaço é de 2 para 100. O que o nosso algoritmo faz é pesquisar esse espaço. Pense em um algoritmo procurando um espaço. Em cada ponto, ele está perguntando... Pense nisso como um passo primitivo. Ele está fazendo uma pergunta e é, na verdade, um teste para saber se é composto. Digamos que este é o número "a". Usaríamos o método de teste de divisão: "n" é divisível por "a"? Nós apenas tentamos isso. Aqui, tentamos dividir "n" por "a" e vemos se o resto é zero, o que significa que "a" seria divisor de "n". E dizemos "Ah, sabemos 100%", levantamos a bandeira e temos 100% de certeza de que é composto. Caso contrário, cada passo não é completamente certo. Pode ser primo, mas não temos certeza, continuamos procurando até chegarmos ao fim. Lembre-se da sua parede. Neste caso, está na raiz quadrada de "n". A pior situação ocorre quando "n" é primo. Nós pesquisamos todos os caminhos para a raiz quadrada de "n", então podemos dizer que ele é primo e temos 100% de certeza. No caso em que "n" é o mesmo múltiplo de dois primos, 7 vezes 7 igual a 49, se jogarmos 49 no nosso algoritmo, ocorre o pior caso. Nós percorremos todo o caminho até a raiz quadrada de "n". Então, vamos para o primeiro conjunto de perguntas. Por exemplo, a Quarta Dimensão pergunta: "(...) uma vez que 2 fosse dado como não divisível, então todos os múltiplos de 2 poderiam ser descartados. O mesmo para 3, 4, 5 etc." Isso é realmente um ponto importante. Nosso antigo algoritmo calculava um passo de cada vez, nós poderíamos estar usando padrões que conhecíamos sobre números compostos, como o que sabemos com certeza. Se o número é divisível por 2, então é composto. Se for maior que 2, então 2 é o número primo. Então podemos dizer que 4 é composto. Eu esqueci do 5 aqui, sinto muito por isso... 4, 6, 8, 10. E, em vez disso, podemos dar um passo como este: 3, 5, 7, 9. Em uma categoria de perguntas, todas tentam reduzir este espaço. Se eliminamos todos os números pares, agora o espaço de busca, em vez de ser até a raiz quadrada de "n", é a raiz quadrada de "n" dividido por 2. Podemos encontrar outros padrões em números compostos, para tentar reduzir ainda mais. Outro tipo de questão diz respeito ao caso em que encontramos uma testemunha composta. Isto é, nós encontramos um "a" que nos permite dizer que sabemos que "n" é composto. Lola disse: "Não sairia do loop logo que o teste de primalidade desse falso em algum ponto?" Sim, isso é totalmente correto e é algo que eu quero fazer. Assim que estivermos fazendo uma busca com passos definidos por qualquer padrão que estejamos usando, encontramos uma testemunha composta. Isso significa que ele passou no teste, e dizemos com 100% de confiança que deve parar antes. Nós paramos e dizemos que terminamos e não vamos continuar a procurar. Essa parada precoce é boa, exceto que não nos ajuda no pior dos casos, que é quando "n" é primo. Nesse caso, a interrupção não nos ajudará. Agora, podemos visualizar como essas melhorias permitem reduzir espaço, assim, impedindo que sejam feitas muitas verificações dentro do computador, e, dependendo do seu computador, reduzindo a quantidade de tempo que leva. Agora eu posso mostrar a visualização que eu montei, que nos permite comparar dois algoritmos baseados em quantos passos ocorrem durante a sua execução. À esquerda, está algoritmo "A", que é divisão por teste e que verifica a partir de 2 para a raiz quadrada de "n". À direita, está o algoritmo "B", que é, digamos, o nosso algoritmo melhorado. Nesse caso, eu tenho aplicado se a seleção é divisível por 2, para fazermos metade do número de passos. Eu também terminei o início desse algoritmo "B". Não é perfeito, eu estou apenas aplicando algumas modificações do usuário para que possamos ver o que acontece. Agora, vou brincar com isso para lhes mostrar. Aqui vemos, conforme desço, o algoritmo "A". Temos a saída, se é composta ou primo. No fundo, você verá o número de passos. A primeira coisa a notar é, no lado direito, que qualquer outro número leva apenas um passo. Nós sabemos por que isso acontece. Se for um número par, como este, ele vai sair. Nosso velho algoritmo levou 314 passos. Nosso novo algoritmo só deu um passo, porque ele verifica se é divisível por 2. Isso parece ser uma boa otimização. No entanto, à medida que construímos a nossa entrada, você perceberá que os passos aumentam e a barra cresce e se torna vermelha. Uma vez que nos aproximamos da região onde estamos indo colidir, essa linha vermelha até aqui é o limite dos passos. Se a barra bate lá, nós falhamos, o que significa que o nosso rover irá quebrar. Nesse caso, o navegador vai realmente quebrar. Vou tentar chegar perto dele. Estou perto dele agora, e ele está correndo muito lentamente, posso sentir que o meu computador está prestes a falhar. Observe que o algoritmo melhorado levou apenas dois passos, mas lembre-se do pior caso. Tem alguns números primos grandes salvos aqui. Por exemplo, temos que ser capazes de lidar com este caso. Nós não sabemos o que estamos jogando em nosso algoritmo. Se eu jogar um grande número primo, veja o que acontece: o algoritmo "B", como se sabe, está tomando metade do número de passos no pior caso, mas ele ainda está usando muitos passos aqui. Porque é o pior caso, certo? Estamos chegando perto de quebrar aqui, e este não é um número primo muito longo. Ainda temos, neste caminho, pelo menos 15 dígitos. Quando coloco este número do primo de 12 dígitos em nosso algoritmo, vamos ver o que acontece. Está lento, vai falhar. Olha só o que aconteceu: ambos os algoritmos ficaram bem em cima do limite. Não funcionou. Nossa alteração no algoritmo ainda não está boa o suficiente, mas agora temos o entendimento do que estamos tentando melhorar, que é o número de passos no pior dos casos. Temos também essa ferramenta legal que nos permite visualizar o quão rápido ele está crescendo, o quão rápido o número de passos cresce, conforme a entrada cresce. Abaixo, eu vou explicar como eu configuro. Assim, você pode configurar o seu algoritmo e compará-lo com o cenário de base e ver muito melhor o que você pode fazer.