Análise de algoritmos - Analysis of algorithms

Para pesquisar uma determinada entrada em uma determinada lista ordenada, tanto o algoritmo de pesquisa binário quanto o linear (que ignora a ordem) podem ser usados. A análise do primeiro e do último algoritmo mostra que leva no máximo log 2 ( n ) e n etapas de verificação, respectivamente, para uma lista de comprimento n . Na lista de exemplos representados de comprimento 33, a pesquisa por "Morin, Arthur" leva 5 e 28 etapas com pesquisa binária (mostrada em ciano ) e linear ( magenta ), respectivamente.
Gráficos de funções comumente usadas na análise de algoritmos, mostrando o número de operações N versus tamanho de entrada n para cada função

Na ciência da computação , a análise de algoritmos é o processo de encontrar a complexidade computacional dos algoritmos - a quantidade de tempo, armazenamento ou outros recursos necessários para executá-los . Normalmente, isso envolve a determinação de uma função que relaciona o comprimento da entrada de um algoritmo ao número de etapas que ele executa (sua complexidade de tempo ) ou ao número de locais de armazenamento que ele usa (sua complexidade de espaço ). Um algoritmo é considerado eficiente quando os valores dessa função são pequenos ou crescem lentamente em comparação com o crescimento no tamanho da entrada. Entradas diferentes com o mesmo comprimento podem fazer com que o algoritmo tenha um comportamento diferente, portanto , as descrições de melhor, pior e média de caso podem ser de interesse prático. Quando não especificado de outra forma, a função que descreve o desempenho de um algoritmo é geralmente um limite superior , determinado a partir das entradas de pior caso para o algoritmo.

O termo "análise de algoritmos" foi cunhado por Donald Knuth . A análise de algoritmos é uma parte importante de uma teoria mais ampla da complexidade computacional , que fornece estimativas teóricas para os recursos necessários para qualquer algoritmo que resolva um determinado problema computacional . Essas estimativas fornecem uma visão sobre direções razoáveis ​​de pesquisa para algoritmos eficientes .

Na análise teórica de algoritmos é comum estimar sua complexidade no sentido assintótico, ou seja, estimar a função de complexidade para dados de entrada arbitrariamente grandes. As notações Big O , Big omega e Big-theta são usadas para esse fim. Por exemplo, a pesquisa binária é executada em um número de etapas proporcionais ao logaritmo do comprimento da lista classificada que está sendo pesquisada, ou em O (log (n)), coloquialmente "em tempo logarítmico ". Normalmente, estimativas assintóticas são usadas porque diferentes implementações do mesmo algoritmo podem diferir em eficiência. No entanto, as eficiências de quaisquer duas implementações "razoáveis" de um determinado algoritmo estão relacionadas por um fator multiplicativo constante chamado de constante oculta .

Medidas exatas (não assintóticas) de eficiência às vezes podem ser calculadas, mas geralmente requerem certas suposições relativas à implementação particular do algoritmo, chamado de modelo de computação . Um modelo de computação pode ser definido em termos de um computador abstrato , por exemplo, máquina de Turing , e / ou postulando que certas operações são executadas em unidade de tempo. Por exemplo, se a lista classificada à qual aplicamos a pesquisa binária tem n elementos, e podemos garantir que cada pesquisa de um elemento na lista pode ser feita em unidade de tempo, então, no máximo log 2 n + 1 unidades de tempo são necessárias para retornar uma resposta.

Modelos de custo

As estimativas de eficiência de tempo dependem do que definimos como uma etapa. Para que a análise corresponda de forma útil ao tempo de execução real, o tempo necessário para executar uma etapa deve ser garantido como sendo limitado acima por uma constante. Deve-se ter cuidado aqui; por exemplo, algumas análises contam a adição de dois números como uma etapa. Esta suposição pode não ser garantida em certos contextos. Por exemplo, se os números envolvidos em um cálculo podem ser arbitrariamente grandes, o tempo necessário para uma única adição não pode mais ser considerado constante.

Geralmente são usados ​​dois modelos de custo:

  • o modelo de custo uniforme , também chamado de medição de custo uniforme (e variações semelhantes), atribui um custo constante a cada operação da máquina, independentemente do tamanho dos números envolvidos
  • o modelo de custo logarítmico , também chamado de medição de custo logarítmico (e variações semelhantes), atribui um custo a cada operação da máquina proporcional ao número de bits envolvidos

Este último é mais complicado de usar, por isso só é empregado quando necessário, por exemplo, na análise de algoritmos aritméticos de precisão arbitrária , como os usados ​​em criptografia .

Um ponto-chave que muitas vezes é esquecido é que limites inferiores publicados para problemas são frequentemente dados para um modelo de computação que é mais restrito do que o conjunto de operações que você poderia usar na prática e, portanto, existem algoritmos que são mais rápidos do que o que seria ingenuamente pensamento possível.

Análise de tempo de execução

A análise de tempo de execução é uma classificação teórica que estima e antecipa o aumento no tempo de execução (ou tempo de execução) de um algoritmo conforme seu tamanho de entrada (geralmente denotado como n ) aumenta. A eficiência do tempo de execução é um tópico de grande interesse na ciência da computação : um programa pode levar segundos, horas ou até anos para terminar de ser executado, dependendo de qual algoritmo ele implementa. Embora as técnicas de criação de perfil de software possam ser usadas para medir o tempo de execução de um algoritmo na prática, elas não podem fornecer dados de temporização para todas as infinitas entradas possíveis; o último só pode ser alcançado pelos métodos teóricos de análise de tempo de execução.

Deficiências de métricas empíricas

Uma vez que os algoritmos são independentes de plataforma (ou seja, um determinado algoritmo pode ser implementado em uma linguagem de programação arbitrária em um computador arbitrário executando um sistema operacional arbitrário ), existem desvantagens adicionais significativas em usar uma abordagem empírica para avaliar o desempenho comparativo de um determinado conjunto de algoritmos.

Tome como exemplo um programa que procura uma entrada específica em uma lista classificada de tamanho n . Suponha que este programa foi implementado no Computador A, uma máquina de última geração, usando um algoritmo de pesquisa linear , e no Computador B, uma máquina muito mais lenta, usando um algoritmo de pesquisa binária . O teste de referência nos dois computadores que executam seus respectivos programas pode ser parecido com o seguinte:

n (tamanho da lista) Tempo de execução do computador A
(em nanossegundos )
Tempo de execução do computador B
(em nanossegundos )
16 8 100.000
63 32 150.000
250 125 200.000
1.000 500 250.000

Com base nesses indicadores, seria fácil para saltar para a conclusão de que o computador A está executando um algoritmo que é muito superior em eficiência ao do Computador B . No entanto, se o tamanho da lista de entrada for aumentado para um número suficiente, essa conclusão é dramaticamente demonstrada como errada:

n (tamanho da lista) Tempo de execução do computador A
(em nanossegundos )
Tempo de execução do computador B
(em nanossegundos )
16 8 100.000
63 32 150.000
250 125 200.000
1.000 500 250.000
... ... ...
1.000.000 500.000 500.000
4.000.000 2.000.000 550.000
16.000.000 8.000.000 600.000
... ... ...
63.072 × 10 12 31.536 × 10 12 ns
ou 1 ano
1.375.000 ns
ou 1.375 milissegundos

O computador A, executando o programa de pesquisa linear, exibe uma taxa de crescimento linear . O tempo de execução do programa é diretamente proporcional ao seu tamanho de entrada. Dobrar o tamanho de entrada dobra o tempo de execução, quadruplicar o tamanho de entrada quadruplica o tempo de execução e assim por diante. Por outro lado, o computador B, executando o programa de pesquisa binária, exibe uma taxa de crescimento logarítmica . Quadruplicar o tamanho da entrada apenas aumenta o tempo de execução em uma quantidade constante (neste exemplo, 50.000 ns). Mesmo que o computador A seja aparentemente uma máquina mais rápida, o computador B inevitavelmente ultrapassará o computador A em tempo de execução porque está executando um algoritmo com uma taxa de crescimento muito mais lenta.

Ordens de crescimento

Informalmente, pode-se dizer que um algoritmo exibe uma taxa de crescimento da ordem de uma função matemática se, além de um certo tamanho de entrada n , a função vezes uma constante positiva fornece um limite superior ou limite para o tempo de execução desse algoritmo. Em outras palavras, para um determinado tamanho de entrada n maior que algum n 0 e uma constante c , o tempo de execução desse algoritmo nunca será maior que . Este conceito é freqüentemente expresso usando a notação Big O. Por exemplo, uma vez que o tempo de execução da classificação por inserção cresce quadraticamente à medida que seu tamanho de entrada aumenta, a classificação por inserção pode ser considerada de ordem O ( n 2 ).

A notação Big O é uma maneira conveniente de expressar o pior cenário para um determinado algoritmo, embora também possa ser usada para expressar o caso médio - por exemplo, o pior cenário para a classificação rápida é O ( n 2 ), mas o tempo de execução de caso médio é O ( n  log  n ) .

Ordens empíricas de crescimento

Assumindo que o tempo de execução segue a regra de potência, t ≈ kn a , o coeficiente a pode ser encontrado tomando medidas empíricas do tempo de execução em alguns pontos do tamanho do problema e calculando de forma que . Em outras palavras, isso mede a inclinação da linha empírica no gráfico log-log do tempo de execução vs. tamanho do problema, em algum ponto do tamanho. Se a ordem de crescimento de fato segue a regra de potência (e assim a linha no gráfico log-log é de fato uma linha reta), o valor empírico de a permanecerá constante em intervalos diferentes, e se não, ele mudará (e a linha é uma linha curva) - mas ainda pode servir para comparação de quaisquer dois algoritmos dados quanto às suas ordens empíricas locais de comportamento de crescimento . Aplicado à tabela acima:

n (tamanho da lista) Tempo de execução do computador A
(em nanossegundos )
Ordem local de crescimento
(n ^ _)
Tempo de execução do computador B
(em nanossegundos )
Ordem local de crescimento
(n ^ _)
15 7 100.000
65 32 1.04 150.000 0,28
250 125 1.01 200.000 0,21
1.000 500 1,00 250.000 0,16
... ... ...
1.000.000 500.000 1,00 500.000 0,10
4.000.000 2.000.000 1,00 550.000 0,07
16.000.000 8.000.000 1,00 600.000 0,06
... ... ...

É claramente visto que o primeiro algoritmo exibe uma ordem linear de crescimento, de fato, seguindo a regra de potência. Os valores empíricos do segundo estão diminuindo rapidamente, sugerindo que ele segue outra regra de crescimento e, em qualquer caso, tem ordens locais de crescimento muito mais baixas (e melhorando ainda mais), empiricamente, do que o primeiro.

Avaliação da complexidade do tempo de execução

A complexidade de tempo de execução para o pior cenário de um determinado algoritmo às vezes pode ser avaliada examinando a estrutura do algoritmo e fazendo algumas suposições simplificadoras. Considere o seguinte pseudocódigo :

1    get a positive integer n from input
2    if n > 10
3        print "This might take a while..."
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "Done!"

Um determinado computador levará um tempo discreto para executar cada uma das instruções envolvidas na execução desse algoritmo. A quantidade específica de tempo para realizar uma dada instrução irá variar dependendo de qual instrução está sendo executada e qual computador está executando, mas em um computador convencional, essa quantidade será determinística . Digamos que as ações realizadas na etapa 1 consomem tempo T 1 , a etapa 2 consome tempo T 2 e assim por diante.

No algoritmo acima, as etapas 1, 2 e 7 serão executadas apenas uma vez. Para uma avaliação de pior caso, deve-se presumir que a etapa 3 também será executada. Assim, a quantidade total de tempo para executar as etapas 1-3 e 7 é:

Os loops nas etapas 4, 5 e 6 são mais difíceis de avaliar. O teste de loop externo na etapa 4 será executado ( n + 1) vezes (observe que uma etapa extra é necessária para encerrar o loop for, portanto, n + 1 e não n execuções), o que consumirá T 4 ( n + 1) tempo . O loop interno, por outro lado, é governado pelo valor de j, que itera de 1 a i . Na primeira passagem pelo loop externo, j itera de 1 a 1: O loop interno faz uma passagem, portanto, executar o corpo do loop interno (etapa 6) consome T 6 tempo, e o teste do loop interno (etapa 5) consome 2 T 5 vezes. Durante a próxima passagem pelo loop externo, j itera de 1 a 2: o loop interno faz duas passagens, portanto, executar o corpo do loop interno (etapa 6) consome 2 T 6 tempo, e o teste do loop interno (etapa 5) consome 3 T 5 vez.

Ao todo, o tempo total necessário para executar o corpo do loop interno pode ser expresso como uma progressão aritmética :

que pode ser fatorado como

O tempo total necessário para executar o teste de loop externo pode ser avaliado de forma semelhante:

que pode ser fatorado como

Portanto, o tempo total de execução para este algoritmo é:

que se reduz a

Como regra geral , pode-se supor que o termo de ordem mais alta em qualquer função dada domina sua taxa de crescimento e, portanto, define sua ordem de tempo de execução. Neste exemplo, n 2 é o termo de ordem mais alta, então pode-se concluir que f (n) = O (n 2 ). Formalmente, isso pode ser provado da seguinte forma:

Provar que





Seja k uma constante maior ou igual a [ T 1 .. T 7 ] Portanto



Uma abordagem mais elegante para analisar este algoritmo seria declarar que [ T 1 .. T 7 ] são todos iguais a uma unidade de tempo, em um sistema de unidades escolhido de forma que uma unidade seja maior ou igual aos tempos reais para essas etapas. Isso significaria que o tempo de execução do algoritmo se divide da seguinte forma:

Análise da taxa de crescimento de outros recursos

A metodologia de análise de tempo de execução também pode ser utilizada para prever outras taxas de crescimento, como o consumo de espaço de memória . Como exemplo, considere o seguinte pseudocódigo que gerencia e realoca o uso de memória por um programa com base no tamanho de um arquivo que esse programa gerencia:

while file is still open:
    let n = size of file
    for every 100,000 kilobytes of increase in file size
        double the amount of memory reserved

Nesse caso, conforme o tamanho do arquivo n aumenta, a memória será consumida a uma taxa de crescimento exponencial , que é a ordem O (2 n ). Esta é uma taxa de crescimento extremamente rápida e provavelmente incontrolável para o consumo de recursos de memória .

Relevância

A análise de algoritmo é importante na prática porque o uso acidental ou não intencional de um algoritmo ineficiente pode afetar significativamente o desempenho do sistema. Em aplicativos sensíveis ao tempo, um algoritmo que demora muito para ser executado pode tornar seus resultados desatualizados ou inúteis. Um algoritmo ineficiente também pode acabar exigindo uma quantidade antieconômica de capacidade de computação ou armazenamento para ser executado, novamente tornando-o praticamente inútil.

Fatores constantes

A análise de algoritmos geralmente se concentra no desempenho assintótico, particularmente no nível elementar, mas em aplicações práticas, fatores constantes são importantes e os dados do mundo real são, na prática, sempre limitados em tamanho. O limite é normalmente o tamanho da memória endereçável, portanto, em máquinas de 32 bits 2 32 = 4 GiB (maior se for usada memória segmentada ) e em máquinas de 64 bits 2 64 = 16 EiB. Assim, dado um tamanho limitado, uma ordem de crescimento (tempo ou espaço) pode ser substituída por um fator constante e, nesse sentido, todos os algoritmos práticos são O (1) para uma constante grande o suficiente ou para dados pequenos o suficiente.

Essa interpretação é útil principalmente para funções que crescem extremamente lentamente: logaritmo iterado (binário) (log * ) é menor que 5 para todos os dados práticos (2 65536 bits); (binário) log-log (log log n ) é menor que 6 para virtualmente todos os dados práticos (2 64 bits); e o log binário (log n ) é menor que 64 para virtualmente todos os dados práticos (2 64 bits). Um algoritmo com complexidade não constante pode, no entanto, ser mais eficiente do que um algoritmo com complexidade constante em dados práticos se a sobrecarga do algoritmo de tempo constante resultar em um fator constante maior, por exemplo, um pode ter tanto quanto e .

Para dados grandes, fatores lineares ou quadráticos não podem ser ignorados, mas para dados pequenos, um algoritmo assintoticamente ineficiente pode ser mais eficiente. Isso é particularmente usado em algoritmos híbridos , como Timsort , que usa um algoritmo assintoticamente eficiente (aqui mesclagem de classificação , com complexidade de tempo ), mas muda para um algoritmo assintoticamente ineficiente (aqui classificação de inserção , com complexidade de tempo ) para pequenos dados, como o mais simples algoritmo é mais rápido em pequenos dados.

Veja também

Notas

Referências

links externos