Python - justificativa do algoritmo

Para fazer afirmações sobre um algoritmo ser eficiente, precisamos de algumas ferramentas matemáticas como prova. Essas ferramentas nos ajudam a fornecer uma explicação matematicamente satisfatória sobre o desempenho e a precisão dos algoritmos. Abaixo está uma lista de algumas dessas ferramentas matemáticas que podem ser usadas para justificar um algoritmo em detrimento de outro.

• Direct Proof:

  É a verificação direta da declaração usando os cálculos diretos. Por exemplo, a soma de dois números pares é sempre um número par. Nesse caso, basta somar os dois números que você está investigando e verificar o resultado como par.

• Proof by induction:

  Aqui, começamos com uma instância específica de uma verdade e a generalizamos para todos os valores possíveis que fazem parte da verdade. A abordagem é pegar um caso de verdade verificada e, em seguida, provar que também é verdadeiro para o próximo caso para a mesma condição dada. Por exemplo, todos os números positivos da forma 2n-1 são ímpares. Nós o provamos para um certo valor de n, então o provamos para o próximo valor de n. Isso estabelece a afirmação como geralmente verdadeira por meio de prova de indução.

• Proof by contraposition:

  Esta prova é baseada na condição Se Não A implica Não B, então A implica B. Um exemplo simples é se o quadrado de n for par, então n deve ser par. Porque se quadrado em n não é par, então n não é par.

• Proof by exhaustion:

  Isso é semelhante à prova direta, mas é estabelecido visitando cada caso separadamente e provando cada um deles. Um exemplo de tal prova é o teorema das quatro cores.