Complexidade e Análise de Algoritmos
A análise de algoritmos quantifica como o tempo de execução e a memória de um algoritmo crescem com o tamanho da entrada, fornecendo o vocabulário assintótico e as ferramentas usadas para comparar algoritmos e identificar problemas inerentemente difíceis.
Definition
A análise de algoritmos é o estudo dos recursos computacionais — principalmente tempo e espaço — que um algoritmo consome em função do tamanho de sua entrada, juntamente com as técnicas usadas para derivar, expressar e comparar esses limites de recursos.
Scope
Esta área abrange a medição e comparação do uso de recursos algorítmicos: notação assintótica (big-O, big-Omega, big-Theta), a solução de recorrências decorrentes de algoritmos recursivos, análise amortizada de sequências de operações e os fundamentos das classes de complexidade computacional e NP-completude conforme se aplicam ao projeto de algoritmos. Aborda o custo no pior caso, no caso médio e amortizado, e a distinção entre problemas tratáveis e intratáveis. A teoria mais ampla da computação (computabilidade, classes de complexidade formal) pertence a um subcampo separado; aqui o foco é analisar algoritmos concretos.
Sub-topics
Core questions
- Como o uso de recursos de um algoritmo é expresso independentemente dos detalhes da máquina e da implementação?
- O que as análises de pior caso, caso médio e amortizada nos dizem?
- Como as recorrências produzidas por algoritmos recursivos são resolvidas para limites assintóticos?
- Como podemos estabelecer limites inferiores mostrando que nenhum algoritmo pode fazer melhor?
- O que significa para um problema ser NP-completo e por que isso é importante para o projeto?
Key concepts
- big-O, big-Omega, big-Theta
- análise de pior caso e caso médio
- relações de recorrência
- teorema mestre
- análise amortizada
- limites inferiores
- tempo polinomial
- NP-completude
Key theories
- Notação assintótica
- Big-O, big-Omega e big-Theta descrevem a taxa de crescimento do uso de recursos à medida que o tamanho da entrada aumenta, abstraindo constantes e termos de ordem inferior para permitir a comparação de algoritmos independente da máquina.
- Tratabilidade e NP-completude
- Problemas solúveis em tempo polinomial são considerados tratáveis; problemas NP-completos são aqueles aos quais todos os problemas em NP se reduzem, e encontrar um algoritmo polinomial para qualquer um resolveria todos, uma questão (P versus NP) que permanece em aberto.
Clinical relevance
A análise de algoritmos orienta cada decisão de engenharia sobre qual algoritmo ou estrutura de dados usar, prevendo como os sistemas escalam à medida que os dados crescem. Reconhecer que um problema é NP-difícil indica aos profissionais que busquem métodos de aproximação, heurísticos ou de casos especiais, em vez de um algoritmo polinomial exato, moldando o trabalho em otimização, agendamento e computação em larga escala.
History
A notação assintótica foi importada para a ciência da computação da teoria analítica dos números e popularizada por Donald Knuth nas décadas de 1960 e 1970. A teoria da NP-completude foi fundada por Stephen Cook (1971) e estendida por Richard Karp (1972), remodelando o projeto de algoritmos em torno da fronteira entre problemas tratáveis e intratáveis.
Debates
- P versus NP
- Se todo problema cujas soluções podem ser verificadas rapidamente também pode ser resolvido rapidamente (P = NP) é a questão central em aberto da ciência da computação teórica; é amplamente conjecturado que P não é igual a NP, mas nenhuma prova existe.
Key figures
- Donald Knuth
- Stephen Cook
- Richard Karp
- Robert Tarjan
Related topics
Seminal works
- cormen2009
- knuth1976bigo
- kleinberg2006
Frequently asked questions
- Qual é a diferença entre análise de pior caso e caso médio?
- A análise de pior caso limita o uso de recursos na entrada mais desfavorável de cada tamanho, fornecendo uma garantia. A análise de caso médio estima o uso esperado de recursos em uma distribuição de entradas, o que pode ser mais representativo do desempenho típico, mas depende de suposições sobre a distribuição da entrada.
- Se um problema é NP-completo, é inútil tentar resolvê-lo?
- Não. NP-completude significa que nenhum algoritmo eficiente é conhecido para o pior caso, mas as instâncias podem frequentemente ser resolvidas com algoritmos de aproximação, heurísticas, algoritmos exponenciais que são rápidos o suficiente na prática, ou explorando uma estrutura especial. Isso sinaliza uma mudança de estratégia, não impossibilidade.