Análise de algoritmo
Análise de eficiência de um algoritmo pode ser realizada em duas fases diferentes, antes e depois da implementação, como
Análise a priori – Isto é definido como análise teórica de um algoritmo. A eficiência de um algoritmo é medida assumindo que todos os outros factores, por exemplo, a velocidade do processador, são constantes e não têm qualquer efeito na implementação.
Uma análise posterior – Define-se como a análise empírica de um algoritmo. O algoritmo escolhido é implementado utilizando linguagem de programação. A seguir, o algoritmo escolhido é executado na máquina do computador alvo. Nesta análise, são recolhidas estatísticas reais como tempo de execução e espaço necessário.
A análise de algoritmo é tratada com a execução ou tempo de execução de várias operações envolvidas. O tempo de execução de uma operação pode ser definido como o número de instruções informáticas executadas por operação.
Algoritmo Complexidade
Suponha X é tratado como um algoritmo e N é tratado como o tamanho dos dados de entrada, o tempo e espaço implementado pelo Algoritmo X são os dois factores principais que determinam a eficiência de X.
Factor Tempo – O tempo é calculado ou medido através da contagem do número de operações chave, tais como comparações no algoritmo de ordenação.
Factor Espaço – O espaço é calculado ou medido através da contagem do espaço máximo de memória requerido pelo algoritmo.
A complexidade de um algoritmo f(N) fornece o tempo de execução e/ou espaço de armazenamento necessário ao algoritmo em relação a N como o tamanho dos dados de entrada.
Complexidade do espaço
Complexidade do espaço de um algoritmo representa a quantidade de espaço de memória necessária ao algoritmo no seu ciclo de vida.
Espaço necessário para um algoritmo é igual à soma dos dois componentes seguintes
Uma parte fixa que é um espaço necessário para armazenar certos dados e variáveis (ou seja, variáveis simples e constantes, tamanho do programa, etc.), que não dependem do tamanho do problema.
Uma parte variável é um espaço necessário para variáveis, cujo tamanho é totalmente dependente do tamanho do problema. Por exemplo, espaço da pilha de recorrência, alocação dinâmica de memória, etc.
Complexidade do espaço S(p) de qualquer algoritmo p é S(p) = A + Sp(I) onde A é tratado como a parte fixa e S(I) é tratado como a parte variável do algoritmo que depende da característica de instância I. Segue-se um exemplo simples que tenta explicar o conceito
Algoritmo
SUM(P, Q)Step 1 - STARTStep 2 - R ← P + Q + 10Step 3 - Stop
Aqui temos três variáveis P, Q e R e uma constante. Daí S(p) = 1+3. Agora o espaço depende dos tipos de dados de determinados tipos de constantes e variáveis e será multiplicado em conformidade.
Time Complexity
Time Complexity de um algoritmo é a representação da quantidade de tempo necessária pelo algoritmo para executar até à conclusão. Os requisitos de tempo podem ser indicados ou definidos como uma função numérica t(N), onde t(N) pode ser medido como o número de passos, desde que cada passo demore um tempo constante.
Por exemplo, em caso de adição de dois números inteiros de n bits, são tomados N passos. Consequentemente, o tempo computacional total é t(N) = c*n, onde c é o tempo consumido para adição de dois bits. Aqui, observamos que t(N) cresce linearmente à medida que aumenta o tamanho de entrada.
