A análise da complexidade de um algoritmo consiste no estudo formal da quantidade de recursos (por exemplo de tempo ou espaço ) necessários à execução deste algoritmo . Isso não deve ser confundido com a teoria da complexidade , que estuda a dificuldade intrínseca dos problemas e não se concentra em um algoritmo particular.
Quando os cientistas quiseram afirmar formal e rigorosamente qual é a eficiência de um algoritmo ou, ao contrário, sua complexidade , perceberam que a comparação de algoritmos entre eles era necessária e que as ferramentas para fazê-lo eram necessárias. Na pré-história da computação (década de 1950), a medição publicada, se existisse, muitas vezes dependia do processador usado, da RAM e dos tempos de acesso à memória de massa , da linguagem de programação e do compilador usado.
Uma abordagem independente de hardware foi, portanto, necessária para avaliar a eficiência dos algoritmos. Donald Knuth foi um dos primeiros a aplicá-lo sistematicamente desde os primeiros volumes de sua série The Art of Computer Programming . Ele completou esta análise com considerações específicas à teoria da informação : esta, por exemplo, combinada com a fórmula de Stirling , mostra que, no pior caso, não é possível realizar, em um vetor de computador, uma classificação geral (isto é , apenas por comparação) de N elementos em um tempo crescente com n mais lentas do que N LN N .
A abordagem mais clássica é, portanto, calcular o tempo de cálculo no pior caso .
Existem pelo menos três alternativas para a análise da complexidade do pior caso. A complexidade média dos algoritmos, baseada em uma distribuição probabilística de tamanhos de dados, tenta estimar o tempo médio que pode ser esperado da avaliação de um algoritmo em dados de um determinado tamanho. A complexidade amortizada das estruturas de dados consiste na determinação do custo das sequências de operações. A análise de algoritmo suave mais recente pretende estar mais perto de situações reais, calculando a complexidade no pior caso em instâncias ligeiramente ruidosas.
Suponhamos que o problema colocado seja encontrar um nome em uma lista telefônica que consiste em uma lista ordenada alfabeticamente. Isso pode ser feito de várias maneiras diferentes. Aqui estão dois:
Para cada um desses métodos, existe um pior caso e um melhor caso. Considere o método 1:
Se o diretório contiver 30.000 nomes, o pior caso exigirá 30.000 etapas. A complexidade no pior caso deste primeiro método para entradas no diretório fornecido é , isso significa que no pior caso, o tempo de cálculo é da ordem de magnitude de : é necessário percorrer todos os nomes de uma vez.
O segundo algoritmo pedirá, na pior das hipóteses, para dividir o diretório em dois, então para dividir esta subparte em dois novamente, e assim por diante até que você tenha apenas um nome. O número de passos necessários será o inteiro imediatamente maior do que o qual, quando é 30.000, é 15 (porque é 32.768). A complexidade (o número de operações) deste segundo algoritmo no pior caso é então , o que significa que a ordem de magnitude do número de operações neste pior caso é o logaritmo baseado no tamanho do diretório l ', ou seja, digamos que, para um diretório cujo tamanho esteja entre e , ele será da ordem de . Também podemos escrever ou , porque e têm a mesma ordem de magnitude.
Para se ter uma ideia das diferentes complexidades, a tabela abaixo apresenta as diferentes classes de complexidade, seus nomes, tempos de execução de referência e um problema dessa complexidade. Os tempos de execução são estimados com base no acesso à memória de 10 nanossegundos por etapa. Os tempos aqui apresentados não têm valor realista, pois durante uma execução em uma máquina muitos mecanismos entram em ação, os tempos são dados a título de indicação para fornecer uma ordem de grandeza do tempo necessário para a execução de tal ou qual algoritmo.
Tempo | Tipo de complexidade | Tempo para n = 5 | Tempo para n = 10 | Tempo para n = 20 | Tempo para n = 50 | Tempo para n = 250 | Tempo para n = 1000 | Tempo para n = 10.000 | Tempo para n = 1.000.000 | Problema de exemplo |
---|---|---|---|---|---|---|---|---|---|---|
complexidade constante | 10 ns | 10 ns | 10 ns | 10 ns | 10 ns | 10 ns | 10 ns | 10 ns | acesso a uma célula de mesa | |
complexidade logarítmica | 10 ns | 10 ns | 10 ns | 20 ns | 30 ns | 30 ns | 40 ns | 60 ns | busca dicotômica | |
complexidade de raiz | 22 ns | 32 ns | 45 ns | 71 ns | 158 ns | 316 ns | 1 µs | 10 µs | teste de primalidade ingênuo | |
complexidade linear | 50 ns | 100 ns | 200 ns | 500 ns | 2,5 µs | 10 µs | 100 µs | 10 ms | Lista de cursos | |
complexidade quase linear | 50 ns | 100 ns | 200 ns | 501 ns | 2,5 µs | 10 µs | 100,5 µs | 10,05 ms | Triangulação de Delaunay | |
complexidade linear | 40 ns | 100 ns | 260 ns | 850 ns | 6 µs | 30 µs | 400 µs | 60 ms | classificações de comparação ideais (como classificação por mesclagem ou classificação por heap ) | |
complexidade quadrática (polinomial) | 250 ns | 1 µs | 4 µs | 25 µs | 625 µs | 10 ms | 1s | 2,8 horas | Navegação de matriz 2D | |
complexidade cúbica (polinomial) | 1,25 µs | 10 µs | 80 µs | 1,25 ms | 156 ms | 10s | 2,7 horas | 316 anos | multiplicação de matriz ingênua | |
complexidade subexponencial | 30 ns | 100 ns | 492 ns | 7 µs | 5 ms | 10s | 3,2 anos | anos | fatoração de inteiros com GNFS (o melhor algoritmo conhecido em 2018) | |
complexidade exponencial | 320 ns | 10 µs | 10 ms | 130 dias | anos | ... | ... | ... | problema de mochila de força bruta | |
complexidade do fator | 1,2 µs | 36 ms | 770 anos | anos | ... | ... | ... | ... | problema do caixeiro viajante com abordagem ingênua | |
complexidade duplamente exponencial | 4,3 s | anos | ... | ... | ... | ... | ... | ... | Decisão aritmética de Presburger |
é o logaritmo iterado .