Complexidade computacional - Computational complexity

Em ciência da computação , a complexidade computacional ou simplesmente complexidade de um algoritmo é a quantidade de recursos necessária para executá-lo. Um foco particular é dado aos requisitos de tempo e memória . A complexidade de um problema é a complexidade dos melhores algoritmos que permitem resolver o problema.

O estudo da complexidade de algoritmos explicitamente dados é chamado de análise de algoritmos , enquanto o estudo da complexidade de problemas é chamado de teoria da complexidade computacional . Ambas as áreas são altamente relacionadas, pois a complexidade de um algoritmo é sempre um limite superior da complexidade do problema resolvido por este algoritmo. Além disso, para projetar algoritmos eficientes, muitas vezes é fundamental comparar a complexidade de um algoritmo específico com a complexidade do problema a ser resolvido. Além disso, na maioria dos casos, a única coisa que se sabe sobre a complexidade de um problema é que ele é menor do que a complexidade dos algoritmos conhecidos mais eficientes. Portanto, há uma grande sobreposição entre a análise de algoritmos e a teoria da complexidade.

Como a quantidade de recursos necessários para executar um algoritmo geralmente varia com o tamanho da entrada, a complexidade é normalmente expressa como uma função n → f ( n ) , onde n é o tamanho da entrada e f ( n ) é o a complexidade do pior caso (o máximo da quantidade de recursos necessários sobre todas as entradas de tamanho n ) ou a complexidade do caso médio (a média da quantidade de recursos sobre todas as entradas de tamanho n ). A complexidade do tempo é geralmente expressa como o número de operações elementares necessárias em uma entrada de tamanho n , onde as operações elementares são assumidas para levar uma quantidade constante de tempo em um determinado computador e mudar apenas por um fator constante quando executadas em um computador diferente. A complexidade do espaço é geralmente expressa como a quantidade de memória exigida por um algoritmo em uma entrada de tamanho n .

Recursos

Tempo

O recurso mais comumente considerado é o tempo. Quando "complexidade" é usada sem qualificação, geralmente significa complexidade de tempo.

As unidades usuais de tempo (segundos, minutos etc.) não são usadas na teoria da complexidade porque são muito dependentes da escolha de um computador específico e da evolução da tecnologia. Por exemplo, um computador hoje pode executar um algoritmo significativamente mais rápido do que um computador da década de 1960; entretanto, esta não é uma característica intrínseca do algoritmo, mas sim uma consequência dos avanços tecnológicos no hardware do computador . A teoria da complexidade busca quantificar os requisitos de tempo intrínsecos dos algoritmos, ou seja, as restrições de tempo básicas que um algoritmo colocaria em qualquer computador. Isso é obtido contando o número de operações elementares que são executadas durante o cálculo. Presume-se que essas operações demorem um tempo constante (ou seja, não são afetadas pelo tamanho da entrada) em uma determinada máquina e costumam ser chamadas de etapas .

Espaço

Outro recurso importante é o tamanho da memória do computador necessária para a execução de algoritmos.

Outras

O número de operações aritméticas é outro recurso comumente usado. Nesse caso, fala-se de complexidade aritmética . Se conhecermos um limite superior no tamanho da representação binária dos números que ocorrem durante um cálculo, a complexidade do tempo é geralmente o produto da complexidade aritmética por um fator constante.

Para muitos algoritmos, o tamanho dos inteiros usados ​​durante um cálculo não é limitado e não é realista considerar que as operações aritméticas demoram um tempo constante. Portanto, a complexidade do tempo, geralmente chamada de complexidade de bits neste contexto, pode ser muito maior do que a complexidade aritmética. Por exemplo, a complexidade aritmética do cálculo do determinante de um n × n matriz de número inteiro é para os algoritmos habituais ( eliminação de Gauss ). A complexidade de bits dos mesmos algoritmos é exponencial em n , porque o tamanho dos coeficientes pode crescer exponencialmente durante o cálculo. Por outro lado, se esses algoritmos forem acoplados à aritmética multimodular , a complexidade de bits pode ser reduzida a O ^~ ( n ⁴ ) . ${\ displaystyle O (n ^ {3})}$

Formalmente, a complexidade de bits se refere ao número de operações em bits que são necessárias para executar um algoritmo. Com a maioria dos modelos de computação , ele iguala a complexidade do tempo a um fator constante. Em computadores , o número de operações necessárias em palavras de máquina também é proporcional à complexidade do bit. Portanto, a complexidade de tempo e a complexidade de bits são equivalentes para modelos realistas de computação

Na classificação e na pesquisa , o recurso geralmente considerado é o número de comparações de entradas. Geralmente, essa é uma boa medida da complexidade do tempo, se os dados forem organizados de maneira adequada.

Complexidade em função do tamanho da entrada

É impossível contar o número de etapas de um algoritmo em todas as entradas possíveis. Como a complexidade geralmente aumenta com o tamanho da entrada, a complexidade é normalmente expressa como uma função do tamanho n (em bits ) da entrada e, portanto, a complexidade é uma função de n . No entanto, a complexidade de um algoritmo pode variar drasticamente para diferentes entradas do mesmo tamanho. Portanto, várias funções de complexidade são comumente usadas.

A complexidade do pior caso é o máximo da complexidade sobre todas as entradas de tamanho n , e a complexidade do caso médio é a média da complexidade sobre todas as entradas de tamanho n (isso faz sentido, como o número de entradas possíveis de um determinado o tamanho é finito). Geralmente, quando a "complexidade" é usada sem ser especificada, esse é o pior caso de complexidade de tempo considerado.

Complexidade assintótica

Geralmente é difícil calcular com precisão o pior caso e a complexidade do caso médio. Além disso, esses valores exatos fornecem pouca aplicação prática, pois qualquer mudança de computador ou de modelo de computação mudaria um pouco a complexidade. Além disso, o uso de recursos não é crítico para valores pequenos de n , e isso faz com que, para n pequeno , a facilidade de implementação seja geralmente mais interessante do que uma complexidade baixa.

Por essas razões, geralmente se concentra no comportamento da complexidade para n grande , ou seja, em seu comportamento assintótico quando n tende para o infinito. Portanto, a complexidade é geralmente expressa usando a notação de O grande .

Por exemplo, o algoritmo usual para multiplicação de inteiros tem uma complexidade de isso significa que há uma constante tal que a multiplicação de dois inteiros de no máximo n dígitos pode ser feita em um tempo menor que Este limite é nítido no sentido de que o pior - a complexidade de caso e a complexidade de caso médio são o que significa que há uma constante tal que essas complexidades são maiores do que A raiz não aparece nesta complexidade, pois a mudança da raiz muda apenas as constantes e${\ displaystyle O (n ^ {2}),}$${\ displaystyle c_ {u}}$${\ displaystyle c_ {u} n ^ {2}.}$${\ displaystyle \ Omega (n ^ {2}),}$${\ displaystyle c_ {l}}$${\ displaystyle c_ {l} n ^ {2}.}$${\ displaystyle c_ {u}}$${\ displaystyle c_ {l}.}$

Modelos de computação

A avaliação da complexidade depende da escolha de um modelo de computação , que consiste em definir as operações básicas que são feitas em uma unidade de tempo. Quando o modelo de computação não é especificado explicitamente, isso geralmente significa uma máquina de Turing com várias fitas .

Modelos determinísticos

Um modelo determinístico de computação é um modelo de computação tal que os estados sucessivos da máquina e as operações a serem realizadas são completamente determinados pelo estado anterior. Historicamente, os primeiros modelos determinísticos eram funções recursivas , cálculo lambda e máquinas de Turing . O modelo de máquinas de acesso aleatório (também chamadas de máquinas RAM) também é amplamente utilizado, como uma contrapartida mais próxima dos computadores reais .

Quando o modelo de computação não é especificado, geralmente é considerado uma máquina de Turing com várias fitas . Para a maioria dos algoritmos, a complexidade do tempo é a mesma em máquinas de Turing com várias fitas e em máquinas RAM, embora alguns cuidados possam ser necessários em como os dados são armazenados na memória para obter essa equivalência.

Computação não determinística

Em um modelo de computação não determinístico , como máquinas de Turing não determinísticas , algumas escolhas podem ser feitas em algumas etapas da computação. Na teoria da complexidade, considera-se todas as escolhas possíveis simultaneamente, e a complexidade não determinística do tempo é o tempo necessário, quando as melhores escolhas são sempre feitas. Em outras palavras, considera-se que o cálculo é feito simultaneamente em tantos processadores (idênticos) quantos forem necessários, e o tempo de cálculo não determinístico é o tempo gasto pelo primeiro processador que finaliza o cálculo. Esse paralelismo é parcialmente adequado à computação quântica por meio de estados emaranhados superpostos na execução de algoritmos quânticos específicos , como, por exemplo, a fatoração de Shor de apenas pequenos inteiros (em março de 2018: 21 = 3 × 7).

Mesmo quando tal modelo de computação ainda não é realista, ele tem importância teórica, principalmente relacionada ao problema P = NP , que questiona a identidade das classes de complexidade formadas tomando pelo menos "tempo polinomial" e "tempo polinomial não determinístico" limites superiores. Simular um algoritmo NP em um computador determinístico geralmente leva "tempo exponencial". Um problema está na classe de complexidade NP , se puder ser resolvido em tempo polinomial em uma máquina não determinística. Um problema é NP-completo se, grosso modo, estiver em NP e não for mais fácil do que qualquer outro problema NP. Muitos problemas combinatórios , como o problema da mochila , o problema do caixeiro-viajante e o problema da satisfatibilidade booleana, são NP-completos. Para todos esses problemas, o algoritmo mais conhecido possui complexidade exponencial. Se qualquer um desses problemas pudesse ser resolvido em tempo polinomial em uma máquina determinística, então todos os problemas NP também poderiam ser resolvidos em tempo polinomial, e um teria P = NP. Em 2017, é geralmente conjecturado que P ≠ NP, com a implicação prática de que os piores casos de problemas NP são intrinsecamente difíceis de resolver, ou seja, demoram mais do que qualquer intervalo de tempo razoável (décadas!) Para comprimentos interessantes de entrada.

Computação paralela e distribuída

A computação paralela e distribuída consiste em dividir a computação em vários processadores, que funcionam simultaneamente. A diferença entre os diferentes modelos reside principalmente na forma de transmissão de informações entre os processadores. Normalmente, na computação paralela a transmissão de dados entre os processadores é muito rápida, enquanto, na computação distribuída, a transmissão de dados é feita através de uma rede e, portanto, muito mais lenta.

O tempo necessário para um cálculo em N processadores é pelo menos o quociente por N do tempo necessário para um único processador. Na verdade, esse limite teoricamente ideal nunca pode ser alcançado, porque algumas subtarefas não podem ser paralelizadas e alguns processadores podem ter que esperar um resultado de outro processador.

O principal problema de complexidade é, portanto, projetar algoritmos de forma que o produto do tempo de computação pelo número de processadores seja o mais próximo possível do tempo necessário para a mesma computação em um único processador.

Computação quântica

Um computador quântico é um computador cujo modelo de computação é baseado na mecânica quântica . A tese de Church – Turing se aplica a computadores quânticos; ou seja, todo problema que pode ser resolvido por um computador quântico também pode ser resolvido por uma máquina de Turing. No entanto, alguns problemas podem ser teoricamente resolvidos com uma complexidade de tempo muito menor usando um computador quântico em vez de um computador clássico. Por enquanto, isso é puramente teórico, pois ninguém sabe como construir um computador quântico eficiente.

A teoria da complexidade quântica foi desenvolvida para estudar as classes de complexidade de problemas resolvidos usando computadores quânticos. É utilizado na criptografia pós-quântica , que consiste em projetar protocolos criptográficos resistentes a ataques de computadores quânticos.

Complexidade do problema (limites inferiores)

A complexidade de um problema é o mínimo das complexidades dos algoritmos que podem resolver o problema, incluindo algoritmos desconhecidos. Portanto, a complexidade de um problema não é maior do que a complexidade de qualquer algoritmo que resolve os problemas.

Segue-se que toda complexidade que é expressa com grande notação O é uma complexidade do algoritmo, bem como do problema correspondente.

Por outro lado, geralmente é difícil obter limites inferiores não triviais para a complexidade do problema e existem poucos métodos para obter esses limites inferiores.

Para resolver a maioria dos problemas, é necessária a leitura de todos os dados de entrada, o que, normalmente, necessita de um tempo proporcional ao tamanho dos dados. Assim, tais problemas têm uma complexidade pelo menos linear , ou seja, usando grande notação ômega , uma complexidade${\ displaystyle \ Omega (n).}$

A solução de alguns problemas, normalmente em álgebra computacional e geometria algébrica computacional , pode ser muito grande. Nesse caso, a complexidade é limitada pelo tamanho máximo da saída, uma vez que a saída deve ser escrita. Por exemplo, um sistema de n equações polinomiais de grau d em n indeterminados pode ter até soluções complexas , se o número de soluções for finito (este é o teorema de Bézout ). Como essas soluções devem ser anotadas, a complexidade desse problema é Para este problema, um algoritmo de complexidade é conhecido, que pode, portanto, ser considerado assintoticamente quase ótimo. ${\ displaystyle d ^ {n}}$ ${\ displaystyle \ Omega (d ^ {n}).}$${\ displaystyle d ^ {O (n)}}$

Um limite inferior não linear de é conhecido pelo número de comparações necessárias para um algoritmo de classificação . Assim, os melhores algoritmos de ordenação são ótimos, pois sua complexidade é Este limite inferior resulta do fato de que há n ! maneiras de ordenar n objetos. Como cada comparação se divide em duas partes, esse conjunto de n ! ordens, o número de N de comparações que são necessárias para distinguir todas as ordens deve verificar o que implica pela fórmula de Stirling . ${\ displaystyle \ Omega (n \ log n)}$${\ displaystyle O (n \ log n).}$${\ displaystyle 2 ^ {N}> n !,}$${\ displaystyle N = \ Omega (n \ log n),}$

Um método padrão para obter limites inferiores de complexidade consiste em reduzir um problema a outro problema. Mais precisamente, suponha que se possa codificar um problema A de tamanho n em um subproblema de tamanho f ( n ) de um problema B , e que a complexidade de A seja Sem perda de generalidade, pode-se supor que a função f aumenta com n e tem uma função inversa h . Então a complexidade do problema B é. Este é o método que é usado para provar que, se P ≠ NP (uma conjectura não resolvida), a complexidade de todo problema NP-completo é para todo inteiro positivo k . ${\ displaystyle \ Omega (g (n)).}$ ${\ displaystyle \ Omega (g (h (n))).}$${\ displaystyle \ Omega (n ^ {k}),}$

Uso em design de algoritmo

Avaliar a complexidade de um algoritmo é uma parte importante do projeto do algoritmo , pois fornece informações úteis sobre o desempenho que pode ser esperado.

É um equívoco comum que a avaliação da complexidade dos algoritmos se tornará menos importante como resultado da lei de Moore , que postula o crescimento exponencial do poder dos computadores modernos . Isso está errado porque este aumento de potência permite trabalhar com grandes dados de entrada ( big data ). Por exemplo, quando se deseja classificar em ordem alfabética uma lista de algumas centenas de entradas, como a bibliografia de um livro, qualquer algoritmo deve funcionar bem em menos de um segundo. Por outro lado, para uma lista de um milhão de entradas (os números de telefone de uma grande cidade, por exemplo), os algoritmos elementares que requerem comparações teriam que fazer um trilhão de comparações, o que levaria cerca de três horas na velocidade de 10 milhões de comparações por segundo. Por outro lado, o quicksort e merge sort requerem apenas comparações (como complexidade de caso médio para o primeiro, como complexidade de pior caso para o último). Para n = 1.000.000 , isso dá aproximadamente 30.000.000 de comparações, o que levaria apenas 3 segundos a 10 milhões de comparações por segundo. ${\ displaystyle O (n ^ {2})}$${\ displaystyle n \ log _ {2} n}$

Assim, a avaliação da complexidade pode permitir a eliminação de muitos algoritmos ineficientes antes de qualquer implementação. Isso também pode ser usado para ajustar algoritmos complexos sem testar todas as variantes. Ao determinar as etapas mais caras de um algoritmo complexo, o estudo da complexidade permite também focar nessas etapas o esforço para melhorar a eficiência de uma implementação.

Veja também

• Complexidade computacional de operações matemáticas

Referências

• Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge , ISBN 978-0-521-42426-4, Zbl  1193.68112
• Du, Ding-Zhu; Ko, Ker-I (2000), Teoria da Complexidade Computacional , John Wiley & Sons , ISBN 978-0-471-34506-0
• Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective , Cambridge University Press
• van Leeuwen, Jan , ed. (1990), Manual de ciência da computação teórica (vol. A): algoritmos e complexidade , MIT Press , ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), Computational Complexity (1ª ed.), Addison Wesley, ISBN 0-201-53082-1
• Sipser, Michael (2006), Introdução à Teoria da Computação (2ª ed.), EUA: Thomson Course Technology , ISBN 0-534-95097-3