Lidar com a complexidade algoritmo

Video: Complexidade de Algoritmos

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

Complexidade	Descrição
O complexidade constante (1)	Fornece um tempo de execução invariável, não importa o quanto de entrada que você fornecer. Cada entrada requer uma única unidade de tempo de execução.
Logarítmica complexidade O (N log N)	O número de operações cresce a uma taxa mais lenta do que a entrada, fazendo com que o algoritmo menos eficiente com pequenas entradas e mais eficiente com os maiores. Um algoritmo típico desta classe é a busca binária.
O complexidade linear (n)	Operações crescer com a entrada em uma proporção de 1: 1. Um algoritmo típico é iteração, quando você digitalizar entrada de uma vez e aplicar uma operação a cada elemento do mesmo.
Linearithmic complexidade O (N log N)	A complexidade é uma mistura entre a complexidade e logarítmica linear. É típico de alguns algoritmos inteligentes utilizados para ordenar os dados, tais como Mergesortsort, heapsort, e Quicksort.
Quadrática complexidade O (n²)	Operações crescer como um quadrado do número de entradas. Quando você tem uma iteração dentro de outra iteração (chamado de iterações aninhadas em ciência da computação), você tem complexidade quadrática. Por exemplo, você tem uma lista de nomes e, a fim de encontrar os mais semelhantes, você comparar cada nome contra todos os outros nomes. Alguns algoritmos de ordenação menos eficientes apresentar tal complexidade: bubble sort, uma espécie de seleção e ordenação por inserção. Este nível de complexidade significa que seus algoritmos podem funcionar por horas ou mesmo dias antes de chegar a uma solução.
Cúbico complexidade O (n³)	Operações crescer ainda mais rápido do que a complexidade quadrática porque agora você tem várias iterações aninhadas. Quando um algoritmo tem esta ordem de complexidade e que você precisa para processar uma quantidade modesta de dados (100.000 elementos), o algoritmo pode funcionar por anos. Quando você tem um número de operações que é uma potência de entrada, é comum para se referir ao algoritmo como sendo executado em tempo polinomial.
Exponencial complexidade O (2ⁿ)	O algoritmo leva o dobro do número de operações anteriores para cada novo elemento adicionado. Quando um algoritmo tem essa complexidade, até mesmo pequenos problemas podem demorar uma eternidade. Muitos algoritmos fazendo buscas exaustivas têm complexidade exponencial. No entanto, o exemplo clássico para este nível de complexidade é o cálculo de números de Fibonacci.
complexidade fatorial O (n!)	Este algoritmo apresenta um verdadeiro pesadelo de complexidade devido ao grande número de combinações possíveis entre os elementos. Imaginem só: Se a sua entrada é de 100 objetos, e uma operação em seu computador leva 10^-6 segundos (a velocidade razoável para todos os computadores hoje em dia), você vai precisar de cerca de 10¹⁴⁰ anos para completar a tarefa com êxito (uma quantidade impossível de tempo porque a idade do universo é estimada como sendo 10₁₄ anos). Um famoso problema complexidade factorial é o problema do caixeiro viajante, em que um vendedor tem que encontrar o caminho mais curto para visitar muitas cidades e voltar para a cidade de partida.