Wolfram Language

Compare algoritmos usando relações assintóticas

Em complexidade computacional, os algoritmos são classificados por seu comportamento para grandes entradas de dados, tipicamente considerados infinitos. Dois algoritmos são comparados se o tempo de execução de um é AsymptoticLessEqual (big ), AsymptoticLess (little ), AsymptoticGreaterEqual (big ) or AsymptoticGreater (little ) que o tempo de execução de outro.

O Problema do caixeiro viajante (PCV) consiste em encontrar a rota mais curta que conecte cidades. Um algoritmo ingênuo tentaria todos as rotas . Um algoritmo HeldKarp melhoraria isso em aproximadamente passos. Mostre que e, portanto, que o algoritmo Held-Karp é mais rápido.

Ambos algoritmos mostram que a classe de complexidade do PCV não é pior que EXPTIME, que são problemas que podem ser resolvidos em tempo . Por exemplo, para qualquer , então o algoritmo Held-Karp tem tempo de execução exponencial.

Para a função fatorial, uma exponencial linear não é suficiente porque .

Entretanto, um fatorial ainda tem tempo de execução exponencial porque .

Soluções aproximadas podem ser encontradas em tempo , então o PCV aproximado está na classe de complexidade P de problemas solúveis em tempo polinomial. Qualquer algoritmo polinomial é mais rápido que um exponencial, ou .

Exemplos Relacionados

de en es fr ja ko zh