Please enable JavaScript.
Coggle requires JavaScript to display documents.
Análise da eficiência de algoritmos - Coggle Diagram
Análise da eficiência de algoritmos
Falamos de dois tipos de eficiências quando analisamos algoritmos:
Complexidade Espacial
e a
Complexidade Temporal
Eficiência espacial significa a quantidade de unidades de memória que o algoritmo utiliza somado ao espaço para sua entrada e sua saída.
Eficiência temporal indica o quão rápido um algoritmo é.
Quase todos os algoritmos são menos rápidos à medida que a entrada cresce.
No entanto, a análise de eficiência pode não depender somente do tamanho da entrada, mas também de quantas operações e como essas operações são feitas sobre essa entrada.
Generalizamos uma métrica para análise de eficiência de algoritmos como checar a magnitude de um único número positivo
n
Identificamos a
operação básica
do algoritmo, que geralmente é a operação característica daquele algoritmo e computamos a quantidade de vezes que essa operação é executada.
Por exemplo, a operação básica de um algoritmo de ordenação é uma
comparação.
Assim, se tivermos o tempo que uma certa máquina executa essa operação básica podemos multiplicar pela quantidade de vezes para obter o tempo de execução do algoritmo.
Ordens de crescimento
A ordem de crescimento quando vamos para entradas de tamanhos maiores vai diferenciar algoritmos eficientes de algoritmos ineficientes.
Por exemplo, um algoritmo com complexidade logarítmica consegue computar uma entrada de 10⁶ em 20 operações, enquanto um de complexidade cúbica vai precisar de 10¹⁸ operações para tal.
Algoritmos de complexidade exponencial, por exemplo, só são práticos para problemas de tamanho muito pequeno.
Melhor caso, pior caso e caso médio
Muitos algoritmos dependem não só do tamanho da entrada, mas também das particularidades dessa entrada.
Por exemplo, a busca sequencial pode ter uma ótima eficiência caso o valor procurado seja o primeiro valor da lista, enquanto pode ter uma péssima eficiência se ele não estiver na lista.
A eficiência de pior caso é a eficiência de um algoritmo quando uma entrada de tamanho n é o pior caso possível para aquele algoritmo. Dá a maior quantidade de operações possível.
A eficiência de melhor caso, em contrapartida, é para uma entrada de tamanho n que seja o melhor caso possível para aquele algoritmo, em que executamos o menor número de operações possível.
O caso médio, por fim, é baseado no comportamento "típico" de um algoritmo e é fortemente atrelado a análise empírica e à probabilidade.
Eficiência Amortizada
Ela fala não por uma só execução do algoritmos mas para uma sequência de operações feitas sobre uma certa estrutura de dados.
Em alguns casos, uma só operação pode ser custosa, mas para o tempo total de uma sequência de N operações, ela é menos custosa que o pior caso daquela operação multiplicado por N.
Portanto, o custo é "amortizado" pela sequência de operações.
Notação assintótica
Temos três notações: O (big Oh), Big Omega & Big Theta.
São, na verdade, funções de alta ordem que recebem outras funções (não negativas) como parâmetro e assim as classificam em subconjuntos.
Big O se refere ao limitante superior, ou seja, a pior complexidade que aquele algoritmo pode assumir.
Podemos usar a notação assintótica para analisar algoritmos que são fietos de duas partes consecutivamente executadas.
Temos classificações de eficiência algortítmica, como Lineares, Logarítmicas, Constantes, Linearítmicas, Potenciais, Quadráticas, Fatoriais e Cúbicas.
Big Omega é o oposto do Big O, pois é o limitante inferior, ou seja, a melhor complexidade que aquele algoritmo pode assumir.
Big Theta é a média (Não literal) entre Big O e Big Omega, pois é similar à função em que tem como argumento.
Tais explicações podem nos fazer entender por que constantes são abstraídas no agrupamento de eficiências.