Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chapter 2 - Fundamentals of the Analysis of Algorithm Efficiency - Coggle…
Chapter 2 - Fundamentals of the Analysis of Algorithm Efficiency
:
2.1 - The Analysis Framework
time efficiency
Indica a rapidez com que um algoritmo em questão é executado.
Para a maioria dos problemas, podemos alcançar progressos muito mais espetaculares em termos de velocidade do que no espaço
space efficiency
Refere-se à quantidade de unidades de memória exigidas pelo algoritmo além do espaço necessário para sua entrada e saída.
A quantidade de espaço extra exigida por um algoritmo normalmente não é tão preocupante, com a ressalva de que ainda existe, é claro, uma diferença entre a memória principal rápida, a memória secundária mais lenta e o cache.
Medir tamanho do input
Para listas, n é o tamanho da lista para problemas de classificação, pesquisa, localização do menor elemento da lista e muitos outros problemas relacionados a listas.
Investigar a eficiência de um algoritmo em função de algum parâmetro n que indica o tamanho da entrada do algoritmo.
Para o problema de avaliação de um polinômio (p(x) = a(n)x^n + ... + a0) de grau n, o número de entradas será o grau do polinômio ou o número de seus coeficientes, que é 1 maior que seu grau.
Ao fazer o produto de duas matrizes, o número de entradas é o número total de elementos N nas matrizes que estão sendo multiplicadas.
Para algoritmo de verificação ortográfica, se o algoritmo examinar caracteres individuais de sua entrada, devemos medir o tamanho pelo número de caracteres; se funcionar por
processando palavras, devemos contar seu número na entrada.
tamanho da entrada para algoritmos que resolvem problemas como a verificação da primalidade de um inteiro positivo n. A entrada é apenas um número, e é a magnitude desse número que determina o tamanho da entrada. Nessas situações, é preferível medir o tamanho pelo número b de bits na representação binária de n:
b = [log2n] + 1. (2.1)
2.2 - Asymptotic Notations and Basic Efficiency Classes
O (big oh)
O(g(n)) é o conjunto de todas as funções com uma ordem de crescimento inferior ou igual a g(n) (dentro de um múltiplo constante, à medida que n vai para o infinito).
(LIMITE SUPERIOR)
Ω(big omega)
Ω(g(n)) representa o conjunto de todas as funções com uma ordem de crescimento superior ou igual a g(n)(dentro de um múltiplo constante, quando n vai para o infinito).(LIMITE INFERIOR)
Θ(big theta).
Θ(g(n)) é o conjunto de todas as funções que têm a mesma ordem de crescimento que g(n) (dentro de um múltiplo constante, quando n vai para o infinito).
(TAXA EXATA DE CRESCIMENTO)
Basic asymptotic efficiency classes
1
constante
log n
logarítmico
n log n
linearítmico
n
linear
n²
quadrática
n³
cúbica
2^n
exponencial
n!
fatorial
2.3 - Mathematical Analysis of Nonrecursive Algorithms
General Plan for Analyzing the Time Efficiency of Nonrecursive Algorithms
1
Decidir um parâmetro (ou parâmetros) que indique o tamanho de uma entrada.
2
Identifique a operação básica do algoritmo. (Como regra, ele está localizado no loop mais interno.)
3
Verificar se o número de vezes que a operação básica é executada depende apenas do tamanho de uma entrada.
Se também depender de alguma propriedade adicional, as eficiências do pior caso, do caso médio e, se necessário, do melhor caso deverão ser investigadas separadamente.
4
Configure uma soma que expresse o número de vezes que a operação básica do algoritmo é executada.
5
Usando fórmulas padrão e regras de manipulação de somas, encontre uma fórmula fechada para a contagem ou, pelo menos, estabeleça sua ordem de crescimento.
2.4 - Mathematical Analysis of Recursives Algorithms
General Plan for Analyzing the Time Efficiency of Recursive Algorithms
1
Decidir um parâmetro (ou parâmetros) que indique o tamanho de uma entrada.
2
Identifique a operação básica do algoritmo.
3
4
5
Resolva a recorrência ou, pelo menos, verifique a ordem de crescimento da sua solução.
Configure uma relação de recorrência, com uma condição inicial apropriada, para o número de vezes que a operação básica é executada.
Verificar se o número de vezes que a operação básica é executada pode variar em diferentes entradas do mesmo tamanho;
se possível, as eficiências do pior caso, do caso médio e do melhor caso devem ser investigadas separadamente.
2.6 - Empirical Analysis of Algorithms
General Plan for the Empirical Analysis of Algorithm Time Efficiency(TESTE/EXP.)
1
2
3
4
5
Gere uma amostra de insumos.
6
7
1 more item...
Execute o algoritmo (ou algoritmos) nas entradas da amostra e registre os dados observados.(Tempo de para cada amostra(quant.) de entradas)
Preparar um programa implementando o algoritmo (ou algoritmos) para a experimentação.
Decida as características da amostra de entrada (seu alcance, tamanho e assim por diante).
Decida a métrica de eficiência M a ser medida e a unidade de medição (uma contagem de operações(quant. entrada) versus uma unidade de tempo).
Compreenda o propósito do experimento.