Lidando com Complexidade de Algoritmo - dummies

Parte de Algoritmos para Dummies Cheat Sheet

Você já sabe que os algoritmos são complexos. No entanto, você precisa saber o quão complexo é um algoritmo porque o mais complexo é, quanto mais demora a ser executado. A tabela a seguir ajuda você a entender os vários níveis de complexidade apresentados em ordem de tempo de execução (do mais rápido ao mais lento).

Complexidade	Descrição
Complexidade constante O (1)	Fornece um tempo de execução invariável, independentemente da quantidade de entrada que você fornecer. Cada entrada requer uma única unidade de tempo de execução.
Complexidade logarítmica O (log n)	O número de operações cresce a uma taxa mais lenta do que a entrada, tornando o algoritmo menos eficiente com pequenas entradas e mais eficiente com as maiores. Um algoritmo típico desta classe é a pesquisa binária.
Complexidade linear O (n)	As operações crescem com a entrada em uma proporção de 1: 1. Um algoritmo típico é a iteração, quando você digitaliza a entrada uma vez e aplica uma operação a cada elemento dela.
Complexidade linearítmica O (n log n)	A complexidade é uma mistura entre a complexidade logarítmica e linear. É típico de alguns algoritmos inteligentes usados ​​para solicitar dados, como Mergesortsort, Heapsort e Quicksort.
Complexidade quadrática O (n 2 )	As operações crescem como um quadrado do número de entradas. Quando você tem uma iteração dentro de outra iteração (chamada iteração aninhada na ciência da computação), você tem complexidade quadrática. Por exemplo, você tem uma lista de nomes e, para encontrar os mais parecidos, você compara cada nome com todos os outros nomes. Alguns algoritmos de ordenação menos eficientes apresentam tal complexidade: tipo de bolha, classificação de seleção e classificação de inserção. Esse nível de complexidade significa que seus algoritmos podem ser executados por horas ou mesmo dias antes de alcançar uma solução.
Complexidade cúbica O (n 3 )	As operações crescem ainda mais rápido do que a complexidade quadrática porque agora você possui várias iterações aninhadas. Quando um algoritmo tem essa ordem de complexidade e você precisa processar uma quantidade modesta de dados (100 000 elementos), seu algoritmo pode ser executado por anos. Quando você tem uma série de operações que é uma potência da entrada, é comum referir o algoritmo como sendo executado em tempo polinomial.
Complexidade exponencial O (2 n )	O algoritmo leva duas vezes o número de operações anteriores para cada novo elemento adicionado. Quando um algoritmo tem essa complexidade, mesmo pequenos problemas podem demorar para sempre. Muitos algoritmos que fazem buscas exaustivas têm complexidade exponencial. No entanto, o exemplo clássico para esse nível de complexidade é o cálculo dos números Fibonacci.
Complexidade fatorial O (n!)	Este algoritmo apresenta um pesadelo real de complexidade devido ao grande número de combinações possíveis entre os elementos. Imagine: se a sua entrada é de 100 objetos e uma operação em seu computador leva 10 -6 segundos (uma velocidade razoável para cada computador hoje em dia), você precisará de cerca de 10 140 anos para completar a tarefa com sucesso (uma quantidade impossível de tempo porque a idade do universo é estimada em 10 14 anos). Um problema de complexidade fatorial famoso é o problema dos vendedores ambulantes, em que um vendedor deve encontrar a rota mais curta para visitar muitas cidades e voltar para a cidade inicial.