Introdução

Entendendo Algoritmos é um livro feito para melhorar a compreensão sobre o funcionamento de algoritmos complexos, dentro vamos ter tópicos importantes como notação Big O, o entendimento de pesquisa binaria e algoritmos como árvores e Dijkstra.

Big O Notation

Vamos logo falar da notação que vai nos acompanhar o livro inteiro. Big O é uma forma de denotar o desempenho de um algoritmo, levando sempre em consideração o pior dos casos, porém, Big O leva em consideração a escalabilidade e execução, exemplo O(n) é melhor que O(n²), mas sem a análise assintótica, não podemos afirmar com total certeza. Análise assintótica é a forma de avaliar o algoritmo conforme o tamanho da entrada cresce.

Porém mesmo sem uma análise assintótica entre O(n) e O(n²), nós conseguimos afirmar qual vai escalar melhor com o tamanho do input.

Exemplo, temos 2 algoritmos que organizam uma estante de livro:

• Algoritmo A O(n): Vai ler uma instrução complexa para cada livro. O "custo fixo" por item é alto.
• Algoritmo B O(n²): A lógica é simplória, quase instantânea, mas você precisa comparar cada livro com todos os outros

Se a estante tem apenas 2 livros, o Algoritmo B O(n²) provavelmente será mais rápido porque a lógica é simples. Mas se a estante tem 1.000 livros, o Algoritmo A O(n) vence, porque ele escala de forma constante, enquanto o outro explode em complexidade.

Existem dois tipos de complexidades que vamos falar bastante na maioria dos algoritmos, sendo elas:

• Complexidade Temporal: É o tempo que a execução cresce de acordo com o tamanho da entrada. Por exemplo, um algoritmo que percorre todos os elementos de uma lista para encontrar o maior valor executa uma operação para cada elemento, caracterizando uma complexidade O(n).
• Complexidade Espacial: É a quantidade de memória adicional que o algoritmo utiliza durante sua execução, além da memória necessária para armazenar os dados de entrada.

Complexidades boas por ordem de melhor para mediana

• O(1) | Constante: É uma constante, não importa se a lista de itens aumenta, ele sempre vai passar por todos pelo menos uma vez, em resumo, não depende do volume de entrada.