Python - Análise de Algoritmo

Análise de Algoritmo

A eficiência de um algoritmo pode ser analisada em dois estágios diferentes, antes e depois da implementação. Eles são os seguintes -

A Priori Analysis- Esta é uma análise teórica de um algoritmo. A eficiência de um algoritmo é medida assumindo que todos os outros fatores, por exemplo, a velocidade do processador, são constantes e não têm efeito na implementação.
A Posterior Analysis- Esta é uma análise empírica de um algoritmo. O algoritmo selecionado é implementado em linguagem de programação. Isso é então executado na máquina do computador de destino. Nesta análise, estatísticas reais, como tempo de execução e espaço necessário, são coletadas.

Complexidade do Algoritmo

Suponha X é um algoritmo e n é o tamanho dos dados de entrada, o tempo e o espaço usados pelo algoritmo X são os dois fatores principais, que decidem a eficiência de X.

Time Factor - O tempo é medido contando o número de operações-chave, como comparações no algoritmo de classificação.
Space Factor - O espaço é medido contando o espaço máximo de memória exigido pelo algoritmo.

A complexidade de um algoritmo f(n) dá o tempo de execução e / ou o espaço de armazenamento exigido pelo algoritmo em termos de n como o tamanho dos dados de entrada.

Complexidade do Espaço

A complexidade de espaço de um algoritmo representa a quantidade de espaço de memória exigida pelo algoritmo em seu ciclo de vida. O espaço exigido por um algoritmo é igual à soma dos dois componentes a seguir -

Uma parte fixa que é um espaço necessário para armazenar certos dados e variáveis, que são independentes do tamanho do problema. Por exemplo, variáveis simples e constantes usadas, tamanho do programa, etc.
Uma parte variável é um espaço requerido por variáveis, cujo tamanho depende do tamanho do problema. Por exemplo, alocação de memória dinâmica, espaço de pilha de recursão, etc.

A complexidade espacial S (P) de qualquer algoritmo P é S (P) = C + SP (I), onde C é a parte fixa e S (I) é a parte variável do algoritmo, que depende da característica de instância I. Seguinte é um exemplo simples que tenta explicar o conceito -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Aqui temos três variáveis A, B e C e uma constante. Portanto, S (P) = 1 + 3. Agora, o espaço depende dos tipos de dados de determinadas variáveis e tipos de constantes e será multiplicado de acordo.

Complexidade de tempo

A complexidade de tempo de um algoritmo representa a quantidade de tempo necessária para que o algoritmo seja executado até a conclusão. Os requisitos de tempo podem ser definidos como uma função numérica T (n), onde T (n) pode ser medido como o número de etapas, desde que cada etapa consuma um tempo constante.

Por exemplo, a adição de dois inteiros de n bits leva npassos. Conseqüentemente, o tempo computacional total é T (n) = c ∗ n, onde c é o tempo gasto para a adição de dois bits. Aqui, observamos que T (n) cresce linearmente conforme o tamanho da entrada aumenta.