Vídeo: As Regras Secretas da Vida Moderna - Algoritmos 2024
Quanto mais operações um algoritmo requer, mais complexo é. A complexidade é uma medida da eficiência do algoritmo em termos de uso do tempo porque cada operação leva algum tempo. Dado o mesmo problema, os algoritmos complexos geralmente são menos favoráveis do que os algoritmos simples porque os algoritmos complexos exigem mais tempo.
Pense nos momentos em que a velocidade de execução faz a diferença, como no setor médico ou financeiro, ou quando voa em piloto automático em um avião ou foguete espacial. A complexidade do algoritmo de medição é uma tarefa desafiadora, embora necessária se você quiser empregar a solução certa. A primeira técnica de medição utiliza máquinas abstratas como a Random Access Machine (RAM).
RAM também significa memória de acesso aleatório, que é a memória interna que seu computador usa ao executar programas. Embora use o mesmo acrônimo, uma máquina de acesso aleatório é algo completamente diferente.
Máquinas abstratas não são computadores reais, mas teóricos, computadores que são imaginados em seu funcionamento. Você usa máquinas abstratas para considerar o quão bem um algoritmo funcionaria em um computador sem testá-lo sobre o real, mas vinculado pelo tipo de hardware que você usaria. Um computador RAM executa operações aritméticas básicas e interage com informações na memória, isso é tudo. Toda vez que um computador de RAM faz qualquer coisa, é preciso um passo de tempo (uma unidade de tempo). Quando você avalia um algoritmo em uma simulação RAM, você conta os passos de tempo usando o seguinte procedimento:
- Contar cada operação simples (aritmética) como um passo de tempo.
- interrompe operações complexas em operações aritméticas simples e contabilize etapas de tempo como definidas na Etapa 1.
- Contagem de todos os dados acessados a partir da memória como um único passo.
Para executar esta contabilidade, você escreve uma versão pseudocódigo do seu algoritmo e execute estas etapas usando papel e lápis. No final, é uma abordagem simples baseada em uma idéia básica de como os computadores funcionam, uma aproximação útil que você pode usar para comparar soluções independentemente da potência e velocidade do seu hardware ou da linguagem de programação que você usa.
Usar uma simulação é diferente de executar o algoritmo em um computador porque você usa uma entrada padrão e predefinida. Medições reais do computador exigem que você execute o código e verifique o tempo necessário para executá-lo. O código de execução em um computador é realmente um ponto de referência, outra forma de medida de eficiência, na qual você também contabiliza o ambiente do aplicativo (como o tipo de hardware usado e a implementação do software).Um benchmark é útil, mas falta generalização. Considere, por exemplo, como o hardware mais recente pode executar rapidamente um algoritmo que levou séculos em seu computador anterior.
