Complexidade exponencial

Definição

Representada por O(2ⁿ). Complexidade algorítmica em que a medida que N aumenta o fator que estiver sendo analisado (tempo ou espaço) aumenta exponencialmente. Algoritmo com complexidade exponencial, não é executável para valores de N muito grandes. Algoritmos desta ordem de complexidade geralmente não são úteis sob o ponto de vista prático. Por exemplo, quando n é vinte, o tempo de execução é cerca de um milhão. Problemas que somente podem ser resolvidos através de algoritmos exponenciais são ditos intratáveis.

Veja também

• Lista de termos referentes aos Algoritmos e Estruturas de Dados
• Análise de Complexidade
• Complexidade

Referências

• Alexandre César Muniz de Oliveira (http://www.deinf.ufma.br/~acmo/grad/ED_complexidade_2005.pdf)
• Análise de Complexidade de Algoritmos

Ligações externas

• Duvidas Frequentes sobre Complexidade
• Ferramenta para Automatização da Análise da Complexidade de Algoritmos
• Complexidade de algoritmos